1059. Prime Factors (25)[素數]——PAT (Advanced Level) Practise

題目信息

1059. Prime Factors (25)

時間限制50 ms
內存限制65536 kB
代碼長度限制16000 B

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

解題思路

枚舉所有素數

AC代碼

#include 
#include 
#include 
using namespace std;
bool prime(long long n){
    long long t = sqrt(n);
    for (long long i = 2; i <= t; ++i){
        if (n%i == 0) return false;
    }
    return true;
}
int main(){
    long long a;
    scanf("%lld", &a);
    printf("%lld=", a);
    if (a == 1){
        printf("1\n");
    }else{
        for (long long i = 2; i <= a; ++i){
            if (prime(i)){
                int k = 0;
                while (a%i == 0){
                    ++k;
                    a /= i;
                }
                if (k == 1){
                    printf("%lld", i);
                }else if (k > 1){
                    printf("%lld^%d", i, k);
                }
                if (k >= 1 && a > 1){
                    printf("*");
                }else if (a == 1){
                    break;
                }
            }
        }
    }
    return 0;
}