本目主要整理素数筛法的若干技巧。
思路
首先需要一个性质：
合数必有素因子 其次，围绕这个定理可以展开相关证明。那么，当再需要判断一个数是否是素数的时候，只需判断它能不能被这些素因子整除。若可以，则不为素数，即为合数。反之，则是素数。
当有了上面的思路之后，我们进步一步的换一个角度，既然所有合数都有素因子，那么当我们获得一个素数时，可以把它的倍数全部标记为合数。这样，当我们判断某一个数是否为素数时，只需判断它是否被标记过即可。这就是素数筛法的大致思想。
问题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] 有两个注意点：
辅助空间大小的开辟大素因子的判断
