2010acm質數.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * 2010 ACM 問題 基本： 如何判斷一個數是不是質數？ 如何尋找質數？ 應用： 如何對一個整數作質因數分解？ 如何對一個階乘作質因數分解？ 質數的定義(復習) 一個大於 1 的整數 p ，如果只有 1 和 p 兩個正因數，則 p 是質數。 A positive integer p greater than 1 is called prime if the only positive factors of p are 1 and p.　　　(取自離散課本) 基本一 判別質數 設要拿來判斷的數為 N： 若 2 ~ (N-1) 中的數都沒辦法整除 N，則 N 是質數。 若 2 ~ √N 中的數都沒辦法整除 N，則 N 是質數。 若 2 ~ √N 中的奇數都沒辦法整除 N，則 N 是質數。 若 2 ~ √N 中的質數都沒辦法整除 N，則 N 是質數。(僅限於已經有√N 以內的質數表可查的情況) 以 97 (質數)為例子… 程式實作 int isprime_1(int check){ if(check == 2)return 1; // 2 is prime int count; for(count = 2; count check; count++){ if( !(check % count) )return 0; // isnt prime } return 1; // is prime }// end of isprime_1 int isprime_2(int check){ if(check == 2)return 1; // 2 is prime int count; int bound = sqrt(check); for(count = 2; count = bound; count++){ if( !(check % count) )return 0; // isnt prime } return 1; // is prime }// end of isprime_2 int isprime_3(int check){ int count; int bound = sqrt(check); if( !(check % 2) ){ if(check != 2)return 0; // isnt prime else return 1; // 2 is prime } for(count = 3; count = bound; count += 2){ if( !(check % count) )return 0; // isnt prime } return 1; // is prime }// end of isprime_3 前面三種檢查範圍的比較 範圍 大小(約略) 如果 N = 106(Worst case) 2 ~ (N-1) N 1,000,000 2 ~ √N √N 1,000 2 ~ √N 的奇數 (√N ) / 2 500 Demo !! (速度比較) 基本二 尋找質數 要決定「N 不是質數」和「N 是質數」哪個做起來比較簡單？ 「N 不是質數」2 ~ √N 中的數只要任一個能整除 N 即可 「N 是質數」2 ~ √N 中的數都不能整除 N 才行 篩法 (Sieve of Eratosthenes) 跳二跳四法 篩法 刪去不是質數的數，剩下的就是質數。 不是質數的數：1、質數的倍數 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 篩法 程式實作 int isprime[1000] = {0}; // prime table(bool or int) isprime[0] = isprime[1] = 1; // 0, 1 are not prime int prime = 2; // filtering while(prime 1000){ int mul = prime * 2; while(mul 1000){ isprime[mul] = 1; // primes multiples mul += p