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

PAT甲级1059 Prime Factors

程序员文章站 2022-03-22 22:21:40
...

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​1​​​k​1​​​​×p​2​​​k​2​​​​×⋯×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​1​​^k​1​​*p​2​​^k​2​​**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
  • 题解:先建立一个一万以内的素数表,然后再从第一个素数开始往后判断是否为n的因子,并统计这个素因子出现的次数。注意特判 n == 1的情况。
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <map>
    #include <vector>
    #define ll long long
    using namespace std;
    map<ll, int> mp;
    vector<ll> v;
    void Prime(ll n){
        mp.clear();
        for(ll i = 2; i <= 10000; i++){
            if(mp[i] == 1) continue;
            v.push_back(i);//i是素数
            for(ll j = i; j <= 10000/i; j++){
                mp[i*j] = 1;
            }
        }
    }
    int main()
    {
        ll n, cnt = 0;
        scanf("%lld", &n);
        if(n == 1){//特例
            printf("1=1\n");
            return 0;
        }
        Prime(n);
        printf("%lld=", n);
        int flag = 0;//flag用于标记是否是第一个素因子,用于输出格式的控制
        for(int i = 0; i < v.size(); i++){
            cnt = 0;
            if(n % v[i] == 0){
                if(flag) printf("*%lld", v[i]);
                else printf("%lld", v[i]);
                flag = 1;
                while(n % v[i] == 0){
                    n /= v[i];
                    cnt++;
                }
                if(cnt > 1){//该素因子个数大于1则输出指数
                    printf("^%lld", cnt);
                }
            }
        }
        printf("\n");
        return 0;
    }
    

     

相关标签: 整数分解