C++ 编程求100000以内素数的个数！···· 请标注注释！····我是新手！··

Question

不要用普通的循环一个个算，如果数据变成一亿或十亿这么算啊

Answer 1

#include <iostream>
using namespace std;
#include <math.h>
int f(int n)//判断n是否为素数，是则返回1，否则返回0
{
if(n<2)return 0;
int i=2;
while(i<=sqrt(n))
if (n%i++==0)return 0;
return 1;
}
void main()
{
int m=1,count=0;
while(m<=100000)
{
if (f(m))count++;
m++;
}
cout<<"100000以内有"<<count<<"个素数"<<endl;
}追问

这么一个个算 效率太低了！···如果数据是一亿呢！···

Answer 2

#include <iostream>
#include "math.h"
using namespace std;
int sushu(int n)
{
int i;
for (i=2;i<=sqrt(n);++i)
if (n%i==0)
return 0;
return 1;
}

int main()
{
int i,c=0;
for (i=2;i<=10000;++i)
if (sushu(i))
++c;
cout<<c;
return 0;
}

Answer 3

#include<iostream>
using namespace std;
int main(){
bool a[100000]={};
int t=0;
for(int i=2;i<100000;i++)
if(a[i]==0)
{
t++;
for(int k=2;i*k<100000;a[i*k]=1,k++);
}
cout<<t;
}
筛法求素数

Answer 4

欧拉筛不更好吗
#include<bits/stdc++.h>using namespace std;const int MAX_N=1e7;int p[MAX_N+10],b[MAX_N+10],tot=0,n;inline int MIN(int a,int b){ return a<b?a:b;
}inline void INIT(){ scanf("%d",&n);
}inline void WORK(){ for(register int i=2;i<n;i++){ if(p[i]==0)b[tot++]=i,p[i]=i; int d=MIN(n/i,p[i]); for(register int j=0;j<tot&&b[j]<=d;++j){ int x=b[j]*i;
p[x]=b[j];
}
}
}inline void PRINT(){ int m; scanf("%d",&m); while(m--){ int x; scanf("%d",&x); if(p[x]==x)cout<<"Yes\n"; else cout<<"No\n";
}
}int main(){
INIT();
WORK();
PRINT(); return 0;
}
这里把100000输入，就能把10000以内的素数保存在数组b中.

Answer 5

突然感觉题主想要的应该是素数筛法。
就是直接生成素数，而不是一个一个数判断是不是素数。
这个效率确实币一个一个判断的nlogn要快很多。