Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 * p2^k2 *…*pm^km.
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 = p1^k1 * p2^k2 *…*pm^km, where pi's are prime factors of N in increasing order, and the exponent ki is the number of pi -- hence when there is only one pi, ki is 1 and must NOT be printed out.
Sample Input:
97532468
Sample Output:
97532468=2^2*11*17*101*1291
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
typedef struct pt{
int base, p;
pt(){
base = ;
p = ;
}
}info;
ll isPrime(ll N){
ll sqr = (ll)sqrt(N * 1.0);
if(N == )
return ;
for(int i = ; i <= sqr; i++){
if(N % i == )
return ;
}
return ;
}
ll primeTB[];
info num[];
ll findPrime(ll tb[], ll maxNum){
int index = ;
for(ll i = ; i <= maxNum; i++){
if(isPrime(i)){
tb[index++] = i;
}
}
return index;
}
int main(){
ll N, sqr, N2;
scanf("%lld", &N);
N2 = N;
sqr = (int)sqrt(1.0 * N) + ;
ll len = findPrime(primeTB, sqr);
int pi = , index = , tag = ;
for(ll i = ; N != && i < len; i++){
tag = ;
while(N % primeTB[i] == ){
N = N / primeTB[i];
num[index].base = primeTB[i];
num[index].p++;
tag = ;
}
if(tag == )
index++;
}
if(N != ){
num[index].base = N;
num[index++].p = ;
}
if(index == ){
num[].base = N;
num[].p = ;
}
printf("%lld=", N2);
printf("%d", num[].base);
if(num[].p > ){
printf("^%d", num[].p);
}
for(int i = ; i < index; i++){
printf("*%d", num[i].base);
if(num[i].p > ){
printf("^%d", num[i].p);
}
}
cin >> N;
return ;
}
总结：
1、判断素数的时候，循环条件为 i <= sqr。
2、生成的质数表可以范围到10^5, 也可以生成到 根号N的范围。
3、15 = 3 * 5，找因子只用找到根号N的范围，如果循环结束N仍然不等于1时，说明它就是大于根号N的一个因子，或者是N本身。