A1059. Prime Factors

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p₁^k₁ * p₂^k₂ *…*p_m^k_m.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

Factor N in the format N = p₁^k₁ * p₂^k₂ *…*p_m^k_m, where p_i's are prime factors of N in increasing order, and the exponent k_i is the number of p_i -- hence when there is only one p_i, k_i is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<math.h>
 5 using namespace std;
 6 typedef long long ll;
 7 typedef struct pt{
 8     int base, p;
 9     pt(){
10         base = 0;
11         p = 0;
12     }
13 }info;
14 ll isPrime(ll N){
15     ll sqr = (ll)sqrt(N * 1.0);
16     if(N == 1)
17         return 0;
18     for(int i = 2; i <= sqr; i++){
19         if(N % i == 0)
20             return 0;
21     }
22     return 1;
23 }
24 ll primeTB[99999999];
25 info num[10000];
26 ll findPrime(ll tb[], ll maxNum){
27     int index = 0;
28     for(ll i = 2; i <= maxNum; i++){
29         if(isPrime(i)){
30             tb[index++] = i;
31         }
32     }
33     return index;
34 }
35 int main(){
36     ll N, sqr, N2;
37     scanf("%lld", &N);
38     N2 = N;
39     sqr = (int)sqrt(1.0 * N) + 1;
40     ll len = findPrime(primeTB, sqr);
41     int pi = 0, index = 0, tag = 0;
42     for(ll i = 0; N != 1 && i < len; i++){
43         tag = 0;
44         while(N % primeTB[i] == 0){
45             N = N / primeTB[i];
46             num[index].base = primeTB[i];
47             num[index].p++;
48             tag = 1;
49         }
50         if(tag == 1)
51             index++;
52     }
53     if(N != 1){
54         num[index].base = N;
55         num[index++].p = 1;
56     }
57     if(index == 0){
58         num[0].base = N;
59         num[0].p = 1;
60     }
61     printf("%lld=", N2);
62     printf("%d", num[0].base);
63     if(num[0].p > 1){
64         printf("^%d", num[0].p);
65     }
66     for(int i = 1; i < index; i++){
67         printf("*%d", num[i].base);
68         if(num[i].p > 1){
69             printf("^%d", num[i].p);
70         }
71     }
72     cin >> N;
73     return 0;
74 }

View Code

总结：

1、判断素数的时候，循环条件为 i <= sqr。

2、生成的质数表可以范围到10^5, 也可以生成到根号N的范围。

3、15 = 3 * 5，找因子只用找到根号N的范围，如果循环结束N仍然不等于1时，说明它就是大于根号N的一个因子，或者是N本身。