#Uva 10179 Irreducible Basic Fractions

#Uva 10179 Irreducible Basic Fractions

簡述

  • 首先先建立質數表

    • 最簡單的想法就是,一開始大家都是 true ,從 2 開始,是 true 就把他的倍數都設成 false

    • 接下來因為 3 不是 2 的倍數,所以是 true , 接下來進去把 3 的倍數設為 false

    • 接下來因為 4 是 false 所以跳過

    • 一直做到 初始化所設的 MAX

    • 如此一來,是 true 的都是 質數

這個方法太慢,用以下方法改善

  • 加速

    • 首先偶數之中只有2是質數 所以除了2以外 只處理奇數

    • 如果現在要篩選的是質數 n 的倍數則從 n * n 開始篩選 每次增加 2n

      • Ex: 篩選5的倍數時 是從25開始 每次增加10

      • 每次增加 2n 的原因很簡單因為如果只增加 n 的話,會變成偶數,而我們已經知道偶數都不是質數了,不需要處理所以直接增加 2n 就好

      • 而從 n * n 開始是為了避免重複篩選 增加效率舉例來說當處理到7時 因為3和5的倍數都已經篩選過了所以7X3=21, 7X5=35這兩個數 就不需要再被篩選一次因此只需要從7X7=49開始

    • 如果想要找到的最大質數是m則只需要檢查到√m就可以了 (國中數學)

缺點: 要用一個很大的 array 紀錄,要找多大的質數,array 就要有多大

Code

尤拉公式

  • 90 = 2 * 3 * 3 * 5

  • 90 (1-1/2)(1-1/3)(1-1/5) = 24

  • 小於 90 與 90 互質 的有 24 個數

此題 Code

if (intput != 1) 那行可以這樣想

假設今天輸入是 7 ,質數表只有 2 3 5 ,則代表輸入是質數

我的github

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *