素数

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int M=100010;
 7 int pri[M],mark[M],pricnt;//mark[i]存i的最小因子，素数时mark[i]==i
 8 void sieve_primes(){//筛素数
 9     pricnt=0;
10     mt(mark,0);
11     mark[0]=mark[1]=1;
12     for(int i=2;i<M;i++){
13         if(!mark[i]) pri[pricnt++]=mark[i]=i;
14         for(int j=0;pri[j]*i<M;j++){
15             mark[i*pri[j]]=pri[j];
16             if(!(i%pri[j])) break;
17         }
18     }
19 }
20 int main(){
21     sieve_primes();
22     int x,y;
23     while(~scanf("%d%d",&x,&y)){
24         if(x==-1&&y==-1) break;
25         int ans=0;
26         for(int i=max(x,2);i<=y;i++){
27             if(mark[i]==i) ans++;
28         }
29         printf("%d
",ans);
30     }
31     return 0;
32 }

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int M=100010;
 7 int pri[M],mark[M],pricnt;//mark[i]存i的最小因子，素数时mark[i]==i
 8 void sieve_primes(){//筛素数
 9     pricnt=0;
10     mt(mark,0);
11     mark[0]=mark[1]=1;
12     for(int i=2;i<M;i++){
13         if(!mark[i]) pri[pricnt++]=mark[i]=i;
14         for(int j=0;pri[j]*i<M;j++){
15             mark[i*pri[j]]=pri[j];
16             if(!(i%pri[j])) break;
17         }
18     }
19 }
20 int main(){
21     sieve_primes();
22     int x,y,px,py;
23     while(~scanf("%d%d",&x,&y)){
24         if(x==-1&&y==-1) break;
25         px=lower_bound(pri,pri+pricnt,x)-pri;
26         py=lower_bound(pri,pri+pricnt,y)-pri;
27         if(pri[py]==y) py++;
28         printf("%d
",py-px);
29     }
30     return 0;
31 }

View Code

Prime Gap http://poj.org/problem?id=3518

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int M=1300000;
 7 int pri[M],mark[M],pricnt;//mark[i]存i的最小因子，素数时mark[i]==i
 8 void sieve_primes(){//筛素数
 9     pricnt=0;
10     mt(mark,0);
11     mark[0]=mark[1]=1;
12     for(int i=2;i<M;i++){
13         if(!mark[i]) pri[pricnt++]=mark[i]=i;
14         for(int j=0;pri[j]*i<M;j++){
15             mark[i*pri[j]]=pri[j];
16             if(!(i%pri[j])) break;
17         }
18     }
19 }
20 int main(){
21     sieve_primes();
22     int n;
23     while(~scanf("%d",&n),n){
24         int L=lower_bound(pri,pri+pricnt,n)-pri;
25         if(pri[L]==n){
26             puts("0");
27         }
28         else{
29             printf("%d
",pri[L]-pri[L-1]);
30         }
31     }
32     return 0;
33 }

View Code

Prime Path http://poj.org/problem?id=3126

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int M=10010;
 7 int pri[M],mark[M],pricnt;//mark[i]存i的最小因子，素数时mark[i]==i
 8 void sieve_primes(){//筛素数
 9     pricnt=0;
10     mt(mark,0);
11     mark[0]=mark[1]=1;
12     for(int i=2;i<M;i++){
13         if(!mark[i]) pri[pricnt++]=mark[i]=i;
14         for(int j=0;pri[j]*i<M;j++){
15             mark[i*pri[j]]=pri[j];
16             if(!(i%pri[j])) break;
17         }
18     }
19 }
20 int n,s,e;
21 bool vis[M];
22 char tmp[8];
23 struct G{
24     int val,step;
25 }now,pre;
26 queue<G> q;
27 void bfs(){
28     mt(vis,0);
29     vis[s]=true;
30     now.val=s;
31     now.step=0;
32     while(!q.empty()) q.pop();
33     q.push(now);
34     while(!q.empty()){
35         pre=q.front();
36         q.pop();
37         if(pre.val==e){
38             printf("%d
",pre.step);
39             return ;
40         }
41         for(int i=0;i<4;i++){
42             for(int j=0;j<10;j++){
43                 if(i==0&&j==0) continue;
44                 sprintf(tmp,"%d",pre.val);
45                 tmp[i]=j+'0';
46                 sscanf(tmp,"%d",&now.val);
47                 if(!vis[now.val]&&mark[now.val]==now.val){
48                     vis[now.val]=true;
49                     now.step=pre.step+1;
50                     q.push(now);
51                 }
52             }
53         }
54     }
55 }
56 int main(){
57     sieve_primes();
58     while(~scanf("%d",&n)){
59         while(n--){
60             scanf("%d%d",&s,&e);
61             bfs();
62         }
63     }
64     return 0;
65 }

View Code

Sum of Consecutive Prime Numbers http://poj.org/problem?id=2739

 1 #include<cstdio>
 2 #include<cstring>
 3 #define mt(a,b) memset(a,b,sizeof(a))
 4 const int M=10010;
 5 int pri[M],mark[M],pricnt;//mark[i]存i的最小因子，素数时mark[i]==i
 6 void sieve_primes(){//筛素数
 7     pricnt=0;
 8     mt(mark,0);
 9     mark[0]=mark[1]=1;
10     for(int i=2;i<M;i++){
11         if(!mark[i]) pri[pricnt++]=mark[i]=i;
12         for(int j=0;pri[j]*i<M;j++){
13             mark[i*pri[j]]=pri[j];
14             if(!(i%pri[j])) break;
15         }
16     }
17 }
18 int main(){
19     sieve_primes();
20     int n;
21     while(~scanf("%d",&n),n){
22         int ans=0;
23         for(int i=0;i<pricnt;i++){
24             int sum=0;
25             for(int j=i;;j++){
26                 sum+=pri[j];
27                 if(sum>=n) break;
28             }
29             if(sum==n) ans++;
30         }
31         printf("%d
",ans);
32     }
33     return 0;
34 }

View Code

end