（笔试题）质数因子Prime Factor

题目：

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.

输入描述:

Each input file contains one test case which gives a positive integer N in the range of long int.

输出描述:

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.

输入例子:

97532468

输出例子:

97532468=2^2*11*17*101*1291

思路：

本题是正整数n的质因子分解问题。n分为3种情况：

1、n=1，特殊数据，既不是质数也不能分解，直接按指定格式输出即可。

2、n是素数，不用分解，直接按指定格式输出即可。要判别n是否为质数，有多种方法，对于本题而言，最简单的方法是使用试商法。因为即使对于n=2147483647=2^31-1范围内的整数，用试商法效率也是很高的，具体参见下面给出的代码。

3、n是大于1的非质数，这正是本题要完成的工作。可以从最小的素数2开始，依次用2,3,4，5，...,sqrt(n)对n进行分解。因为当对2进行分解时，后面关于2的倍数的其他数字也就不能被n整除了，因此也就只对质数的进行计算，记得每次结束某个数字的因式分解之后，更新一下sqrt(n)。

当然，可以考虑采用筛法，事先把一定范围内的质数全部筛选出来，存入数组，然后只用这些质数去分解n，效率会相应提高很多。

（4）本题还有一点需要注意，即打印的格式。

代码：

在线测试:http://www.nowcoder.com/questionTerminal/ea8f62f661554099baed9baa471c6883?orderByHotValue=1&done=0&pos=6&onlyReference=false

AC代码：

#include<iostream>

#include<math.h>

using namespace std;

bool isPrime(int n){

    if(n<2)

        return false;

    int k=int(sqrt(n+0.0));

    for(int i=2;i<=k;i++){

        if(n%i==0)

            return false;

    }

    return true;

}

void PrimeFactor(int n){

    cout<<n<<"=";

    if(n==1){

        cout<<n<<endl;

    	return;

    }

    if(isPrime(n)){

        cout<<n<<endl;

		return;

    }

    int k=int(sqrt(n+0.0));

    int exp=0;

    bool first=true;

    for(int i=2;i<=k;i++){

        exp=0;

        if(n%i==0){

            while(n%i==0){

                n=n/i;

                ++exp;

            }

            if(first){

                if(exp>=2) cout<<i<<"^"<<exp;

                else cout<<i;

                first=false;

            }

            else{

                if(exp>=2) cout<<"*"<<i<<"^"<<exp;

                else cout<<"*"<<i;

            }

            k=int(sqrt(n+0.0));

        }

    }

    if(n>1) cout<<"*"<<n;

    cout<<endl;

}

int main(){

    int n;

    while(cin>>n){

        PrimeFactor(n);

    }

    return 0;

}

巴特西

（笔试题）质数因子Prime Factor

题目：

思路：

代码：

最新文章

热门文章