数论知识(1)-------------素数打表

素数打表，总结了两种形式。

一种是传统的在一个数组里进行标记，进行判断。

一种是直接将素数放进一个数组里。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 
 5 
 6 int prime[1000003],size=0;
 7 int s[1000003];
 8 
 9 void make_ini() //素数打表。直接装在一个数组里面
10 {
11     int i,j;
12     memset(s,0,sizeof(s));
13     for(i=2;i<=1000000;i++)
14     {
15         if(s[i]==0)
16         {
17             prime[++size]=i;
18             j=i*2;
19             for(j;j<=1000000;j+=i)
20             s[j]=1;
21         }
22     }
23 }
24 
25 void sc()
26 {
27     int i;
28     for(i=2;i<=100;i++)
29     if(s[i]==0) printf("%d ",i); //利用s进行打表
30 }
31 
32 int main()
33 {
34     make_ini();
35     sc();
36     return 0;
37 }

View Code