因本人在（10月4日T3）被判断质数暴虐后便决定将判断质数所有办法全列举出来：

1.死亡暴力枚举：

bool is_prime(int n){
	if (n < 2) return false;
	for (int i = 2; i <= n; i++)
		if (n % i == 0) return false;
	return true;
}

绝对不要用此方法！！真的！！

时间复杂度O(N*N);

2.朴素算法：

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

最好别用，除非数字小

时间复杂度O(N*√N);

3.普通筛法：

int primes[N], cnt;                
void get_prime(int n){
    for(int i = 2; i <= n; i ++){ 
        for(int j = i + i; j <= n; j += i) st[j] = true;  
    }
}

可以解决80%的题了

时间复杂度O(n*logn)

4.埃式筛法：

bool st[N];          
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue; 
        for (int j = i + i; j <= n; j += i)
            st[j] = true;    
    }
}

可以解决95%的题了

时间复杂度O(nlog(logn))（本人大力推荐）

5.欧拉筛法（线性筛）：

int primes[N], cnt;     
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        for (int j = 0; primes[j] * i <= n; j ++ ) {
            st[primes[j] * i] = true; 
            if (i % primes[j] == 0) break; 
        }
    }
}

可以解决99.999999%的题了

时间复杂度O(n)（较难理解）