1059. Prime Factors (25)-PAT class A

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 = 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:
Sample Output:

Give an integer and output its multiplication formula decomposed into prime factor in the order of small to large
Analysis: first, establish a prime number table within 500000, and then judge whether it is its prime number from 2. If it is, continue to judge whether i is the prime number of a by a=a/i, and output the prime factor and number after judgment. Use state to judge whether the factor has been input, and output "*" before input

#include <cstdio>
#include <vector>
using namespace std;
vector<int> prime(500000, 1);
int main() {
    for(int i = 2; i * i < 500000; i++)
        for(int j = 2; j * i < 500000; j++)
            prime[j * i] = 0;
    long int a;
    scanf("%ld", &a);
    printf("%ld=", a);
    if(a == 1) printf("1");
    bool state = false;
    for(int i = 2; a >= 2;i++) {
        int cnt = 0, flag = 0;
        while(prime[i] == 1 && a % i == 0) {
            a = a / i;
            flag = 1;
        if(flag) {
            if(state) printf("*");
            printf("%d", i);
            state = true;
        if(cnt >= 2)
            printf("^%d", cnt);
    return 0;

Conclusion: in this question, the first stereotype thinking always thinks of judging prime numbers, so it takes too long to directly list all the ones within 5000 that are not prime numbers, which is a lot more convenient. I'm very good at water.

Posted on Thu, 30 Apr 2020 18:26:53 -0700 by Popgun