Super Prime

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2404&cid=1151
View Code
 1 #include<stdio.h>  
 2 #define max 100000  
 3 int a[max], b[max], c[max] ;  
 4 int main()  
 5 {  
 6     for(int i=0; i<max; i++)  
 7     {  
 8         a[i] = 1 ;  
 9         b[i] = 0 ;  
10     }  
11     a[0] = 0 ;  
12     a[1] = 0 ;  
13     int k = 2 ;  
14     while(k<=max)  
15     {  
16         int t = k ;  
17         while(t<=max)  
18         {  
19             t = t + k ;  
20             if(t<=max)  
21             a[t] = 0 ;  
22         }  
23         k++ ;  
24         while(a[k]==0&&k<=max)  
25         k++ ;  
26     }  
27     k = 0 ;  
28     for(int i=1; i<=max; i++)  
29     if(a[i])  
30     {  
31         k++ ;  
32         c[k] = i ;  
33     }  
34     for(int i=1; i<k; i++)  
35     {  
36         int t = c[i] ;  
37         int j = i ;  
38         while(t<=max)  
39         {  
40             j++ ;  
41             t = t + c[j] ;  
42             if(t<=max&&a[t]&&b[t]==0)  
43             b[t] = 1 ;  
44         }  
45     }  
46     int T, n ;  
47     scanf("%d", &T) ;  
48     for(int i=1; i<=T; i++)  
49     {  
50         scanf("%d", &n) ;  
51         printf("Case %d: ", i) ;  
52         if(b[n])  
53         printf("yes\n") ;  
54         else  
55         printf("no\n") ;  
56     }  
57     return 0 ;  
58 }