PAT 解题报告 1059. Prime Factors (25)

题目描述:

对一个数字(long long)进行质因素分解. 如97532468=2^2*11*17*101*1291

算法分析:

我的方法是(1) 利用质数表求的所有sqrt(N) 以内的质数 (2) 对每个质数看是否能被N整除(测试是不是N的质因子). 并且统计指数次数.

注意点:

之所以可以用(1)是因为即使N有大于sqrt(N)的质因素, 比如10 = 2 * 5, 那么对于这个质因数, 一定有一个对应的小于sqrt(N)的质因数比如这里的2. 得到2的话, 输出留下的N即可, 比如10, 求得小雨sqrt(10)的质数是2, 3, 整除掉2以后剩下5, 输出5即可.

另外注意N本身就是质数的情况, 还有N == 1的特例.

 

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on July 6, 2013