Posted on 2009-03-13 19:44
Hero 閱讀(445)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //1123 Accepted 46 1052 838 C++
2 //分解質因數
3
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <string.h>
7 #include <math.h>
8
9 const int size = 1001000 ;
10 bool isprim[size] ;
11
12 int innum ;
13 int inn ;
14
15 void TestPrime()
16 {
17 isprim[1] = false ;
18 for( int i=1; i<size; i++ ) isprim[i] = true ;
19
20 int maxi = size / 2 ;
21 for( int i=2; i<=maxi; i++ )
22 {
23 if( !isprim[i] ) continue ;
24 for( int j=2; j*i<size; j++ ) isprim[j*i] = false ;
25 }
26 }
27
28 int main()
29 {
30 TestPrime( ) ;
31
32 while( scanf( "%d", &innum ) != EOF )
33 {
34 while( innum -- )
35 {
36 scanf( "%d", &inn ) ; char *blank = "" ;
37
38 for( int i=2; i<=inn; i++ )
39 {
40 if( 1 == inn ) break ;
41 if( isprim[i] )
42 {
43 while( 0 == inn % i )
44 {
45 printf( "%s%d", blank, i ) ;
46 inn = inn / i ;
47 blank = "*" ;
48 }
49 }
50 }
51 printf( "\n" ) ;
52 }
53 }
54 return 0 ;
55 }