c素数を求める
以下はメモです.
素数を求めて、私はプログラムの運行の時間を記録して、異なるアルゴリズムの効率を比較します.後でよく更新するかもしれません.最適なアルゴリズムがあれば、貼り付けます.
もう一つのアルゴリズムは、algorithms in c書のコードで、以下の通りです.100万、1秒程度、残念ながらNが大きいと定義すると配列がオーバーフローする.
素数を求めて、私はプログラムの運行の時間を記録して、異なるアルゴリズムの効率を比較します.後でよく更新するかもしれません.最適なアルゴリズムがあれば、貼り付けます.
#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 ("
%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書のコードで、以下の通りです.100万、1秒程度、残念ながら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;
}