素数小结

判断素数

#include<iostream>
#include<math.h>
using namespace std;
bool su(int n){
	int i=2;
	if(n==1)
		return false;
	for(i=2;i<=sqrt(n);i++){
		if(n%i==0)
			break;
	}
	if(i>sqrt(n))
		return true;
else
	return false;
}

素数筛

埃氏筛

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

欧拉筛

bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i);
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}