HDU 1164 Eddy's research I

题意：给你一个数，让你用它的素数质因子表示出来。

思路：先打一下表，因为会有重复的质因子，所以从大到小开始找，并且找到一个之后不能就接着往下找，要再找一遍这个数。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <iostream>
 5 
 6 using namespace std ;
 7 
 8 int IsPrime[65536] ;
 9 
10 void sett()
11 {
12     int i,j;
13     for(i = 0 ; i <= 65535 ; ++i)
14         IsPrime[i] = true;
15     IsPrime[0] = IsPrime[1] = false ;
16     for(i = 2 ; i <= 65535 ; ++i)
17     {
18         if(IsPrime[i])
19         {
20             for(j = 2*i ; j <= 65535 ; j += i)
21                 IsPrime[j]=false;
22         }
23     }
24 }
25 int main()
26 {
27     int n ;
28     int a[65536] ;
29     sett() ;
30     while(scanf("%d",&n)!= EOF)
31     {
32         int cnt = 1 ;
33         for(int i = 65535 ; i > 1 ; i--)
34         {
35             if(n%i == 0 && IsPrime[i])
36             {
37                 a[cnt++] = i ;
38                 n /= i ;
39                 i++ ;
40             }
41         }
42         printf("%d",a[cnt-1]) ;
43         for(int i = cnt-2 ; i >= 1; i--)
44         {
45             printf("*%d",a[i]) ;
46         }
47         printf("
") ;
48     }
49     return 0 ;
50 }

View Code