素数筛选

一般判断素数的方法是从2开始到sqrt(n)判断是否有数为n的因子若有则说明该数是非素数

1     bool Is_Prime = true;
2     for (int i = 2; i * i < N; i++)
3     {
4         if (N % i == 0)
5             Is_Prime = false;
6     }

比较号的方法是利用筛法选素数

这种方法叫厄拉多塞素数筛选

 1 bool Prime[100000];
 2 void Make_Prime(int N)
 3 {
 4     fill(Prime, Prime + N+1, true);
 5     for (int i = 2; i<N;i++)
 6     {
 7         if (!Prime[i])continue;
 8         for (int j = 2; i * j <N; j++)
 9             Prime[i * j] = false;
10     }
11 }