1 #include <iostream.h>
2 #include <math.h>
3 #define YES 1
4 #define NO 0
5 int is_prime1(int x)
6 {
7 int *prime=new int[x];
8 prime[0]=2;
9 int count=1;
10 for(int i =3;i<=x;i++)
11 {
12 double sqrt_i=sqrt(i);
13 for (int j=0;prime[j]<=sqrt_i;j++)
14 {
15 if(x%prime[j]==0) return 0;
16 }
17 prime[count++]=i;
18 }
19 return 1;
20 }
21 int is_prime2(int x)
22 {
23 int *sieve =new int[x+1];
24 int count=1;
25 int prime;
26 for (int i=0;i<=x;i++)
27 {
28 if (i&0x01)
29 {
30 sieve[i]=YES;
31 }
32 else
33 sieve[i]=NO;
34 }
35 for (i=0;i<=x;i++)
36 {
37 if (sieve[i])
38 {
39 prime=2*i+3;
40 count++;
41 for (int k=prime;k<=x;k+=prime)
42 {
43 sieve[k]=NO;
44 }
45 }
46 }
47 if (sieve[x]==YES)
48 {
49 return 1;
50 }
51 else return 0;
52
53 }
54 void main()
55 {
56 int x;
57 do{
58 cin>>x;
59 if(is_prime2(x))
60 {
61 cout<<x<<endl;
62 }
63 }while(x!=0);
64 }
for more information please view :http://en.wikipedia.org/wiki/Primality_test