学步园

几道简单的关于素数的题目，嘿嘿，基本都是用了筛选法

#include<iostream>
#include<math.h>
#define MAXN 1000001
using namespace std;
bool prime[MAXN];
void init()
{
    prime[1]=false;
    prime[2]=true;
for(int i=3; i<MAXN; i++)
if(i%2)  prime[i]=true;
else  prime[i]=false;
for(int i=3; i<=sqrt((double)MAXN); i++)
   {   
if(prime[i])
for(int j=i+i; j<MAXN; j+=i) prime[j]=false;
   }
}
int main()
{
int a,d,k;
    init();
while(scanf("%d %d %d",&a,&d,&k)==3&&(a||d||k))
    {
int count=0,i;
for(i=a;i<MAXN;)
        {
if(prime[i]) count++;
if(count==k) break;
            i+=d;
        }
        printf("%d\n",i);
    }
return 0;
}

pku2739

将10000以内的素数重新保存在prime[]中，中间判断素数的方法，是用该数整除已经求得的素数来判断

    #include<stdio.h>
    #include<math.h>
#define N 10005
int prime[1300],num[N];
int main()
    {
int n,sum,count;
int i,j,k;
for(i=3,k=1,prime[0]=2;i<10000;i++)
        {
for(j=0;prime[j]*prime[j]<=i;j++)
            {
if(i%prime[j]==0)
break;
            }
if(prime[j]*prime[j]>i)
                    prime[k++]=i;
        }
while(scanf("%d",&n)==1 && n!=0)
        {
            count=0;
for(i=0;i<1229 && i<=n ;i++)
            {
for(j=i,sum=0;sum<=n && j<1229;j++)
                {
                    sum+=prime[j];
if(sum==n)
                        count++;
                }
            }
            printf("%d\n",count);
        }
return 0;
    }

 

pku2262

    #include<stdio.h>    
int main()
    {
bool num[1000001]={0};
int i,j,n;
for(i=2;i<1000;i++)
        {
if(!num[i])//num[i]!=0
            {
for(j=i;j*i<1000000;j++)
                {
                    num[j*i]=1;
                }
            }
        }
while(scanf("%d",&n)==1 && n!=0)
        {
for(i=3;i<n;i+=2)
            {
if(!num[i] && !num[n-i]&& (n-i)%2==1 && i%2==1 )
                {
                    printf("%d = %d + %d\n",n,i,n-i);
break;
                }
            }
        }
return 0;
    }