判断素数#

1
#include<iostream>
2
#include<math.h>
3
using namespace std;
4
bool su(int n){
5
  int i=2;
6
  if(n==1)
7
    return false;
8
  for(i=2;i<=sqrt(n);i++){
9
    if(n%i==0)
10
      break;
11
  }
12
  if(i>sqrt(n))
13
    return true;
14
else
15
  return false;
16
}

素数筛#

埃氏筛#

1
bool isnp[MAXN]; // is not prime: 不是素数
2
void init(int n)
3
{
4
    for (int i = 2; i * i <= n; i++)
5
        if (!isnp[i])
6
            for (int j = i * i; j <= n; j += i)
7
                isnp[j] = 1;
8
}

欧拉筛#

1
bool isnp[MAXN];
2
vector<int> primes; // 质数表
3
void init(int n)
4
{
5
    for (int i = 2; i <= n; i++)
6
    {
7
        if (!isnp[i])
8
            primes.push_back(i);
9
        for (int p : primes)
10
        {
11
            if (p * i > n)
12
                break;
13
            isnp[p * i] = 1;
14
            if (i % p == 0)
15
                break;
16
        }
17
    }
18
}