素数判断

试除法

$$时间复杂度 : O(\sqrt{n})$$

def IsPrime(n: int) -> bool:
    if n < 2:
        return False
    for i in range(2, math.floor(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

bool isPrime(int n)
{
	if (n < 2)	return false;
	for (int i=2;i<=n/i;i++)
		if (!(n % i))	return false;
	return true;
}

埃氏筛法

$$时间复杂度: O(MX loglog MX)$$

MX = 10 ** 6 + 1
prime = []
isPrime = [True] * MX

def getPrime():		# 预处理    
    isPrime[0] = isPrime[1] = False
    for i in range(2, MX):
        if isPrime[i]:
            prime.append(i)
            for j in range(i*i, MX, i):
                isPrime[j] = False

const int N = 1e5 + 10;
vector<int> primes;
bool isPrime[N];

void getPrime()
{
    memset(isPrime, true, sizeof isPrime);
    isPrime[0] = isPrime[1] = false;
    for (int i=2;i<N;i++)
    {
        if (isPrime[i])
        {
            primes.push_back(i);
            for (int j=i*i;j<N;j+=i)    isPrime[j] = false;
        }
    }
}

欧拉筛法 (线性筛)

$$时间复杂度: O(MX)$$

MX = 10 ** 6 + 1
prime = []
isPrime = [True] * MX

def getPrime():		# 预处理    
    isPrime[0] = isPrime[1] = False
    for i in range(2, MX):
        if isPrime[i]:
            primes.append(i)
        # 每个数乘上 <= lpf[x] 的质数
        # 第一个 x % i == 0 =>  i 是 lpf[x]
        for prime in primes:
            if i*prime >= MX:
                break
                isPrime[p*i] = False
            if !(x % i):	# 之所以该算法是线性的,是因为每个 i*prime 只会被它的最小质因子prime筛一次
                break

const int N = 1e5 + 10;
vector<int> primes;
bool isPrime[N];

void getPrime()
{
    memset(isPrime, true, sizeof isPrime);
    isPrime[0] = isPrime[1] = false;
    for (int i=2;i<N;i++)
    {
        if (isPrime[i]) primes.push_back(i);
        for (int prime : primes)
        {
            if (i * prime >= N) break;
            isPrime[i * prime] = false;
            if (!(i % prime))   break;
        }
    }
}