欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT1059:Prime Factors

程序员文章站 2022-07-15 14:01:11
...

1059. Prime Factors (25)

时间限制
100 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
HE, Qinming

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

思路

按指定格式打印一个数的所有素(质)数因子。
1.先初始化建立一个素数表。
2.从2开始,不断用素数i除输入的数num,能够整除说明满足条件,用cnt记录被整除的次数。
3.对于第一个除数的输出进行判断来决定在除数前面是否加"*"。
4.cnt > 2就在当前除数后加"^cnt"。
5.重复2.3.4直至num < 2。
注:对于1要进行特殊处理,不然输出为"1=",正确输出应该是"1=1"。
代码
#include<iostream>
#include<vector>
using namespace std;

vector<int> isPrime(666666,1);

void Init()
{
    for(int i = 2; i * i < 666666; i++)
    {
        for(int j = 2; j*i < 666666; j++)
        {
            isPrime[i * j] = 0;
        }
    }
}

int main()
{
    Init();
    long long num;
    cin >> num;
    cout << num <<"=";
    if(num == 1)
        cout << 1;
    bool first = true;
    for(int i = 2; num >= 2; i++)
    {
        int cnt = 0;
        if(isPrime[i] == 1 && num % i == 0)
        {
            while(num % i == 0)
            {
                cnt++;
                num = num/i;
            }
            if(first)
                first = false;
            else
                cout << "*";
            cout << i;
            if(cnt > 1)
                cout << "^" << cnt;
        }
    }
}