Posted on 2009-09-27 09:37
Hero 閱讀(172)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm
簡單題 素數測試
1 // A .CPP_VS Accepted 269 ms 8339 kb
2
3 #include <stdio.h>
4 #include <stdlib.h>
5
6 const int size = 1100000 ;
7 int isPrime[size+100] ;
8
9 int QUEprime[size] ;
10 int QUEsize ;
11
12 int ina, inb ;
13
14 void Init_isPrime()
15 {
16 isPrime[0] = isPrime[1] = 0 ;
17 for( int i=2; i<size; i++ ) isPrime[i] = 1 ;
18
19 int maxi = size / 2 ;
20 for( int i=2; i<=maxi; i++ )
21 {
22 if( !isPrime[i] ) continue ;
23 for( int j=2; i*j<size; j++ )
24 {
25 isPrime[i*j] = 0 ;
26 }
27 }
28
29 QUEsize = 0 ;
30 for( int i=2; i<size; i++ )
31 {
32 if( isPrime[i] )
33 {
34 QUEsize ++ ;
35 QUEprime[QUEsize] = i ;
36 }
37 }
38 }
39
40 int main()
41 {
42 Init_isPrime() ;
43
44 while( scanf( "%d %d", &ina, &inb ) != EOF )
45 {
46 int suma = 0 ; int sumb = 0 ;
47 int prima = 0 ; int primb = 0 ;
48
49 for( int i=1; i<=QUEsize; i++ )
50 {
51 if( QUEprime[i] > ina ) break ;
52 if( 0 == ina % QUEprime[i] )
53 {
54 suma += QUEprime[i] ;
55 prima = QUEprime[i] ;
56 while( 0 == ina % QUEprime[i] )
57 {
58 ina = ina / QUEprime[i] ;
59 }
60 }
61 }
62
63 for( int i=1; i<=QUEsize; i++ )
64 {
65 if( QUEprime[i] > inb ) break ;
66 if( 0 == inb % QUEprime[i] )
67 {
68 sumb += QUEprime[i] ;
69 primb = QUEprime[i] ;
70 while( inb % QUEprime[i] )
71 {
72 inb = inb / QUEprime[i] ;
73 }
74 }
75 }
76
77 int outa = prima - (suma - prima) ;
78 int outb = primb - (sumb - primb) ;
79
80 if( outa >= outb )
81 {
82 printf( "a\n" ) ;
83 }
84 else
85 {
86 printf( "b\n" ) ;
87 }
88 }
89
90 return 0 ;
91 }