1059. Prime Factors (25)

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

=======================================================
就是一个找质数的问题，其实很简单啦~
切记从小的这头开始尝试，因为试想一下，除掉2，3这种小数字之后，需要尝试的明显少了N多！

#include 
#include 
using namespace std;
const int prime[] =
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
const int prime_length = 25;
map primeMap;
bool isPrime(long val)
{
    for(int i=0; i 0)
        return primeMap[val];
    //没办法了只能苦算
    for(long x=val/2; x>1; x--)
    {
        if(val%x == 0)
        {
            //合数
            primeMap.insert(pair(val, false));
            return false;
        }
    }
    primeMap.insert(pair(val, true));
    return true;
}
map factorCountMap;  //<素数，指数>
int main()
{
    long input;
    scanf("%ld", &input);
    printf("%ld=", input);
    //
    if(input == 1)
    {
        printf("1");
        return 0;
    }
    //从2开始计算...
    long divisor = 2;
    while(input > 1)
    {
        if(!isPrime(divisor))
        {
            divisor++;
            continue;
        }
        if(input%divisor == 0)
        {
            //有这个素数因子
            if(factorCountMap.count(divisor) > 0)
            {
                factorCountMap[divisor] = factorCountMap[divisor] + 1;
            }
            else
            {
                factorCountMap[divisor] = 1;
            }
            input /= divisor;
        }
        else
            divisor++;
    }
    map::iterator it = factorCountMap.begin();
    for(; it!=factorCountMap.end(); it++)
    {
        if(it != factorCountMap.begin())
            printf("*");
        pair p = *it;
        long factor = p.first;
        long exponent = p.second;
        printf("%ld", factor);
        if(exponent > 1)
            printf("^%ld", exponent);
    }
    return 0;
}

Leave a Reply Cancel reply