C++素数判定

质数_百度百科

定义：

素数（也成质数）是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

1.

循环，将n除以2---n-1的整数，如果有其中一个数运算后的余数==0，n不为素数。

#include
using namespace std;
int main()
{
	int n;
	cin>>n;
	bool flag=1;
	for(int i=2;i 
2.
 
开根号：
 
素数的因子只有1和它本身。 如果数c不是素数，则还有其他因子。设a,b.定有一个大于sqrt(c) ，一个小于sqrt(c) 。所以m一定有一个小于等于其平方根的因数，那么验证素数时就只需要验证到其平方根就可以了。
 
#include
using namespace std;
int main()
{
	int n;
	cin>>n;
	bool flag=1;
	for(int i=2;i 
3.
 
埃氏筛法 
 
埃拉托斯特尼筛法_百度百科
 
要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。 
 
#include
using namespace std;
bool flag[104];
int main()
{
    memset(flag,1,sizeof(flag));
    flag[1]=0;
    for(int i=2;i<=sqrt(100);i++){
        if(flag[i]){
            for(int j=2;j*i<=100;j++)flag[i*j]=0;
        }
    }
    for(int i=1;i<=100;i++){
        if(flag[i])cout<<"YES"< 
4.
 
欧拉筛法： 
 
找到一个素数后，就将它的倍数标记为合数，也就是把它的倍数筛掉；如果一个数没有被比它小的素数筛掉，那它就是素数。
 
欧拉筛法复杂度为线性。
 
代码详见例题。
 
例题：
 
素数个数
 
素数个数 - 洛谷
 
题目描述 
求 1,2,⋯,N 中素数的个数。
 
输入格式 
一行一个整数 N。
 
输出格式 
一行一个整数，表示素数的个数。
 
题解：
 
数据范围是10的8次方，不能一个一个判断，要用欧拉筛法。
 
#include
using namespace std;
int n,ans,prime[5800001];
bool visit[100000001];
int main() 
{
	cin>>n;
	if(n<2){
		cout<<0;
		return 0;
	}
	for(register int i=2; i<=n;i++) {
		if(!visit[i])prime[++ans]=i;
		for(register int j=1; prime[j]*i<=n&&j<=ans; ++j) {
			visit[i*prime[j]]=true;
			if(!(i%prime[j])) break;
		}
	}
	//for(int i=1; i<=ans; ++i) printf("%dn",prime[i]);
	cout<