nyoj 快速查找素数

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int prime[2000010];
 4 void puan_prime()
 5 {
 6     
 7     for(int i=2;i<=2000010;i++)
 8     {
 9         if(!prime[i])
10         {
11             for(int j=i+i;j<=2000010;j+=i)
12             prime[j]=1;
13         }
14     }
15 }
16 int main()
17 {
18     int n;
19     puan_prime();
20     while(~scanf("%d",&n),n)
21     {
22         printf("2");
23         for(int i=3;i<=n;i++)
24         if(prime[i]==0)
25         printf(" %d",i);
26         printf("\n");
27     }
28 }

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int prim[2000010];
 4 int pos[2000010];
 5 
 6 void puan_prime()
 7 {
 8     int num=0;
 9     for(int i=2;i<=2000010;i++)
10     {
11         if(!prim[i])
12         {
13             num++;
14             pos[num]=i;
15         }
16         for(int j=1;j<=num&&i*pos[j]<=2000010;j++)
17         {
18             prim[i*pos[j]]=1;
19             //if(i%pos[j]) break;
20         }
21     }
22 }
23 int main()
24 {
25     int n;
26     puan_prime();
27     while(~scanf("%d",&n),n)
28     {
29         printf("%d",pos[1]);
30         for(int i=2;pos[i]<=n;i++)
31         printf(" %d",pos[i]);
32         printf("\n");
33     }
34     
35 }