问题概要
功能:输入一个正整数,按照从小到大的顺序输出它的所有质因子(重复的也要列举)(如180的质因子为2 2 3 3 5 )
数据范围: 1<= n <= 2000 000 014
对应牛客网HJ6 质数因子
思路分析
这个问题的比较简单,这里就不啰嗦了,不过我想简单说说为什么我遍历的范围是2到根号n,而不是2到n。
要取质数因子,简单来说明,就是n=abc*…。其中,a,b,c,…等就是质数因子。若n为质数,则n = 1n,也可以写成n=ab。
也就是说,n最少也是a和b的乘积。若a大于根号n,那么b就势必小于根号n,否则ab的值就会大于n,这是错误的。
所以说,在n=ab这个公式中,至少有一个值是小于根号的(考虑到后面还会乘以c,乘以d等,小于根号n的值也许不止一个)。
代码实现
#include <stdio.h>
#include <math.h>
// 输出质数因子
void printPrimeFactors(int n) {
int i;
// 枚举,从2到根号n
for (i = 2; i <= sqrt(n); i++) {
while (n % i == 0) {
printf("%d ", i);
n = n/i;
}
}
// 如果最后n 大于1,则说明n是个质数
if (n > 1) {
printf("%d", n);
}
}
int main() {
int n;
// 输入整数n
scanf("%d", &n);
if (n >= 1 && n <= 2000000014) {
printPrimeFactors(n);
} else {
printf("输入的整数超出边界!");
}
return 0;
}
注
以上便是对于整数N的质数因子的求解方式,希望对你有所帮助。
感谢阅读w