本目主要整理素數篩法的若干技巧。
思路
首先需要一個性質：
合數必有素因子 其次，圍繞這個定理可以展開相關證明。那么，當再需要判斷一個數是否是素數的時候，只需判斷它能不能被這些素因子整除。若可以，則不為素數，即為合數。反之，則是素數。
當有了上面的思路之后，我們進步一步的換一個角度，既然所有合數都有素因子，那么當我們獲得一個素數時，可以把它的倍數全部標記為合數。這樣，當我們判斷某一個數是否為素數時，只需判斷它是否被標記過即可。這就是素數篩法的大致思想。
問題1
[jobdu-1163]
思路
常規的辦法不說了，下面主要說一下素數篩法的系列。
代碼
#include <iostream>#include <cstring>const int maxn = 10000;bool mark[maxn + 8]; // mark[i]==true表示非素數，標記的是素數的倍數，都是合數。int PRime_table[maxn + 8];int prime_cnt;void init(){ std::memset( mark, 0, sizeof(mark) ); for(int i = 2; i <= maxn; ++i ){ if(mark[i]) continue; // 非素數 else{ // 加入素數 prime_table[prime_cnt++] = i; // 標記非素數 for(int j = i*i; j <= maxn; j += i){ mark[j] = true; } } }}int main(){ int n; init(); while(std::cin >> n){ bool first = true; for(int val = 2; val < n; ++val){ if(!mark[val] && val%10==1){ if(first){ std::cout << val; first = false; } else std::cout << " " << val; } } if(first) std::cout << -1 << std::endl; else std::cout << std::endl; } return 0;}上面的代碼需要注意一點：下面這段標記代碼，應該是把素數i的倍數全部標記為合數，應該是int j = i*2; j <= maxn; j+=i開始。但是，j = i*i的原因在于，對于任意k < i, int j = i*k，當k是素數的時候，j就已經被標記過了，所以沒有必要重復標記。注意即可。
// 加入素數 prime_table[prime_cnt++] = i; // 標記非素數 for(int j = i*i; j <= maxn; j += i){ mark[j] = true; }
題目2
[jobdu-1047]
思路
素數篩法即可。
代碼
#include <iostream>#include <cstring>#include <climits>const unsigned maxn = 1024;bool mark[maxn + 1];void init(){ std::memset( mark, 0, sizeof(mark) ); for(int i = 2; i < maxn; ++i){ if(mark[i]) continue; else{ for(int j = i*i; j<= maxn; j +=i){ mark[j] = true; } } }}int main(void){ int val = 0; init(); while(std::cin >> val){ if(val < 2) std::cout << "no" << std::endl; else if(mark[val]) std::cout << "no" << std::endl; else std::cout << "yes" << std::endl; } return 0;}問題3
參看以下這篇鏈接， 這是leetcode的問題。有一些和上面不同的問題。[Count Primes]
問題4（分解素因數）
[jobdu-1207]
思路
開心！這個題之前都沒有用素數篩法做對過。 思路沒什么好說的，只不過這個題引入了一個新的問題是：分解素因數 這依賴于定理：
合數一定可以分解為素因子相乘的形式 根據這個定理，我們知道對于一個合數可以全部分解為素因子的形式。那么本體的問題就是求解這個分解表達式，即對于任意一個數x，分解為如下的形式：其中p1,p2,?pn均為素數。
x=pe11?pe22…penn
代碼的思路并不難，要是拿到素數表之后，挨個除即可。 但是有個問題是，這個素數表，你要開多大？
那么需要如下的定理來解決這個問題，：
對于任意一個數x，其大于x√的素因子至多為1個。 否者，這兩個大于x√的因子相乘肯定是要大于x的。 所以，對于邊界 N = 1000000000。我們只需找到小于N??√的素因子即可。如果一個數在除過以上的素因子之后沒有變成1，那么證明它還有一個大素因子，此時在最后的結果 + 1即可。
所以，素數表空間的開辟，我們選擇maxn =100000，這就是為什么要這么寫的原因。 還有第二個點要說的是，對于int j = i*i，當i = maxn的時候，j是會越界的。所以，建議還是改用之前的形式。int j = i*2。其實，早上那道題，也是這里修改之后才過的。
出了一個小bug是：index < prime_cnt這個條件寫錯了。如果存在大素因子，這樣數組不就越界了。
代碼
#include <iostream>#include <cstring>const int maxn = 100000;bool marker[maxn+1];int prime_cnt;int prime_table[maxn+1];void init(){ std::memset(marker, 0, sizeof(marker)); prime_cnt = 0; for(int i = 2; i <= maxn; ++i){ if(marker[i]) continue; else{ prime_table[prime_cnt++] = i; for(int j = i*2; j <= maxn; j += i){ marker[j] = true; } } }}int main( void ){ int n = 0; init(); while(std::cin >> n){ int ans = 0; int index = 0; while(n != 1 && index < prime_cnt){ while(n!= 1 && n % prime_table[index] == 0) { ++ans; n /= prime_table[index]; } ++index; } if(n!=1) ++ans; // 存在大素因子 std::cout << ans << std::endl; } return 0;}問題4（ugly number）
參考這篇鏈接：[ugly number] 有兩個注意點：
輔助空間大小的開辟大素因子的判斷
