筛选素数

筛选素数

普通筛法

埃拉托斯特尼筛法，这种筛法虽然很好，但是有些数会被重复访问，比如30，会被素数2、3、5访问

  1. #define N 1000100
  2. #define LL long long
  3. int num[N], prim[N];
  4. int pn = 0;
  5. void table(){
  6.     memset(num, -1, sizeof(num));
  7.     for (int i = 2; i < N; i++) 
  8.         if (num[i]) {
  9.             prim[pn++] = i;
  10.             for (LL j = 1LL*i*i; j < N; j += i) 
  11.                 if (num[j])
  12.                     num[j] = 0;
  13.         }
  14. }

欧拉筛

这个筛法做到了去除重复访问，原理是 if (i % prim[j] == 0) break; 做到每个数只被最小质因数访问。

  1. #define N 100100000
  2. #define LL long long
  3. int num[N], prim[N];
  4. int pn = 0;
  5. void table(){
  6.     memset(num, 0, sizeof(num));
  7.     for (int i = 2; i < N; i++) {
  8.         if (!num[i])
  9.             prim[pn++] = i;
  10.         for (int j = 0; j < pn && 1LL* i * prim[j] <= N; j++){
  11.             num[i * prim[j]] = 1;
  12.             if (i % prim[j] == 0) break;
  13.         }
  14.     }
  15. }