（c语言）求快速算素数的方法。

求一种最省时的方法算10000000内的素数，并存在数组中。

//规模较大时，筛选法确实比较快
#include
#include
using namespace std;
#define MAX_NUM 1000000
#define MAX_N 10000000

int main()
{

int *P;
bool *B;
int M, N, i, j, t, sqrtN;
bool flag;
P = (int *)malloc(sizeof(int)* MAX_NUM);
B = (bool*)malloc(sizeof(int)* MAX_N);
for (i=0;i B[0] = B[1] = false;
P[0]=2;//第一个素数
P[1]=3;
M=2;//数组中素数个数
sqrtN = (int)sqrt(MAX_N);
for (N=3;N {
i=1;
flag = true;
t=(int)sqrt(N) ;
while (P[i]<=t)
{
if (N%P[i]==0)
{
flag = false;
break;
}
i++;
}
if (flag)
{
P[M++]=N;
if (M>MAX_NUM)
{
cout<<"too large"< exit(0);
}
}
}
for (i=0;i {
for (j=2;j<=MAX_N/P[i];j++)
{
B[j*P[i]]=false;
}
}
t=0;j=0;
for (i=0;i {
if (B[i]==true)
{
P[j++]=i;
t++;
}
}
return 0;
}

看一个数能不能被从2到此数的0.5次方的这些数整除，能则不是，不能就是了

判断是不是素数，素数就是只能被1和本身整除的自然数。

void main() { int m,i,k; printf("please input a number:\n"); scanf("%d",&m); k=sqrt(m); for(i=2;i<k;i++) if(m%i==0) break; if(i>=k) printf("该数是素数"); else printf("该数不是素数"); }

#include "stdio.h" void main() { int i, j; for(i=3;i<=10000000;i++) { for(j=2;i*i<=j;j++) if(i%j==0) break; if(j>=i) printf("%d\t",i); } }

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息