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

 #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本身。

巴特西

A1059. Prime Factors

最新文章

热门文章