C语言:素数,判断2-200 0000之间有多少素数,限时2秒,至多5秒,求解答?

发布网友发布时间：2024-10-06 13:17

共4个回答

热心网友时间：2024-10-11 11:23

//#include "stdafx.h"//vc++6.0加上这一行.
#include "stdio.h"
void main(void){
char *pa;
int i,j,n=2000001,sum;
if((pa=(char *)malloc(sizeof(char)*n))==NULL){
printf("Application memory failure...\n");
exit(0);
}
for(i=1;i<n;pa[i++]=1);
for(sum=0,i=2;i<n;i++)
if(pa[i]){
for(j=i+i;j<n;pa[j]=0,j+=i);
sum++;
}
free(pa);
printf("Between 2 to 2000000 a total of %d prime.\n",sum);
}

热心网友时间：2024-10-11 11:28

可用筛选法，很快。

热心网友时间：2024-10-11 11:27

以下程序极快，0.001 秒就运行完毕：

#include <stdio.h>
#include <stdbool.h>

#define MAX 2000000L

bool flag[MAX + 1]; // flase 表示是素数

int main()
{
long i, j, n = 1;
for (i = 3; i <= MAX; i += 2)
  if (!flag[i])
  {
n++;
   for(j = i*3; j <= MAX; j += (i<<1))
    flag[j] = true;
  }
printf("%ld\n", n); // 输出：148933
return 0;
}

热心网友时间：2024-10-11 11:28

#include <stdio.h>
#include <math.h>
main()
{
int n,m,count=0;
for(n=2;n<=2000;n++)
for(m=2;m<=sqrt(n);m++)
if(n%m==0)
{
count++;
break;
}
count=1999-count;
printf("%d\n",count);
}