c 求素数

以下是一些笔记。

求素数的，我会记录下程序运行的时间，比较不同算法的效率。以后可能会常更新的。如果有最优的算法，我会贴出来的。

 

 

#include "stdio.h"                    //2百万以内 24秒
#include "math.h"
void main()
{
	long i,j,k,temp;
	int f;
	k=3;
	printf ("2 ");
	while (k<2000000)
	{ 
		temp=sqrt(k);
		f=1;
		for (i=3;i<=temp;i++)
		{
			if (k % i ==0 )
			{
				f=0;
				break;
			}
		}
		if (f==1)
			printf ("%d ",k);
		k+=2;
	}
}

 

 

 

#include "stdio.h"    //1000,000   27秒,速度慢且占用空间 
#include "math.h"   //保存己知的素数，由已知用x % 素数  
#define dd 100000
void main()
{
long N=1000;
unsigned long i,j,temp,k,kk;
unsigned long ed[dd];
int f;

for (i=0;i<dd;i++)
 ed[i]=0;

ed[0]=2;
k=3;
kk=1;
while (k<N)
{   
	f=1;
	temp=(k+1)/2;
	for (j=0;ed[j]!=0,ed[j]<temp;j++)
	{
		if  (k % ed[j]==0 ) 
		{
			f=0;
			break;
		}
	}
	if (f==1)
	{
		printf ("%d ",k);
		ed[kk]=k;
		kk++;
	}
	k+=2;
}
printf ("\n%d",kk);
}

 

 

 

#include "stdio.h"                    //2百万数据量，不保存数组 22秒
#include "math.h"
void main()
{
	long i,j,k,temp;
	int f;
	k=3;
	printf ("2 3 ");
	while (k<2000000)
	{   
		if ( (k % 3 ==0) || (k % 5==0) ) 
		{
			k+=2;
			continue;
		}
	
		temp=sqrt(k);
		f=1;
		for (i=3;i<=temp;i+=2)
		{
			if (k % i ==0 )	
			{
				f=0;
				break;
			}
		}
		if (f==1)
			printf ("%d ",k);
		k+=2;
	}
}

 

#include "stdio.h"    //筛选法,听说效率不错，
#define N 10000    //但是本人不知如何在c里面用bool型，望高手赐教
main()
{

int shu[N];
int i,j,temp,k;
for (i=2;i<=N;i++)
 shu[i]=1;

temp=N/2;
for(i=2;i<=temp;i++)
 if (shu[i]==1)
  {
   printf ("%d ",i);
   k=i;
   while (k<N)
    {
     shu[k]=0;
     k+=i;
     }
   }

system("pause");

}

 

另一种算法，在 algorithms in c 书的代码，如下。一百万，一秒左右，可惜当N 定义为很大时，数组溢出.

#include "stdio.h"
#define N 1000000
main()
{
	char shu[N];
	int i,j;
	for (i=2;i<N;i++)
		shu[i] = 1;
	for (i=2;i<N;i++)
		if (shu[i])
			for (j=2;j*i<N;j++)
				shu[j*i] = 0;
}