提问人：Aisa.Imn 提问时间：10/27/2016 最后编辑：chqrlieAisa.Imn 更新时间：4/2/2021 访问量：3540
求给定数的所有质因数
Find all prime factors of a given number
问：
我想找到一个数的所有质因数，例如 或 .8: 2 2 212: 2 2 3
所以我写了这段代码：
#include <stdio.h>
int main() {
int a, triangularNum, n;
scanf("%d", &triangularNum);
for (a = 2; a <= n; ++a) {
while (n % a == 0) {
n = triangularNum;
printf("%d\t", a);
n = n / a;
}
}
}
但是，当它的因数幂> 1 时，它只会多次打印该因数。
答：
4赞
Milack27
10/27/2016
#1
如果你删除这个，你的代码就可以正常工作了：triangularNum
#include <stdio.h>
int main()
{
int a, n;
scanf("%d", &n);
for (a=2; a<=n; ++a)
{
while(n%a==0)
{
printf("%d\t", a);
n = n/a;
}
}
}
0赞
Gaurav Chaudhry
8/6/2020
#2
下面的代码可以更快地找到给定数字的所有质因数。
#include <stdio.h>
#include <math.h>
int main()
{
int a, n;
scanf("%d", &n);
int sqroot = (int)sqrt(n);
while (n % 2 == 0)
{
n = n / 2;
printf("%d\t", 2);
}
for (a=3; a<=sqroot; a+=2)
{
while(n%a==0)
{
printf("%d\t", a);
n = n/a;
}
}
}
检查给定整数 n 的素数的最基本方法称为试除法。此方法将 n 除以从 2 到 n 的平方根的每个整数。任何这样的整数将 n 均匀地除以 n 作为复合数;否则，它是素数。不需要检查大于平方根的整数，因为每当 n = a ⋅ b 时，两个因子 a 和 b 中的一个小于或等于 n 的平方根。另一个优化是仅检查素数作为此范围内的因子。https://en.wikipedia.org/wiki/Prime_number
评论
1赞
Adrian Mole
8/6/2020
虽然这段代码可以解决这个问题，但包括解释它如何以及为什么解决这个问题，将真正有助于提高你的帖子的质量，并可能导致更多的赞成票。请记住，您是在为将来的读者回答问题，而不仅仅是现在提问的人。请编辑您的答案以添加解释，并指出适用的限制和假设。
0赞
Richard Tran
10/15/2023
此方法需要一个边缘情况来检查 n 是否仍然大于 2。在这种情况下，n 是质数。
0赞
Amisha Sahu
4/2/2021
#3
void factor(int n){
if(n<=1) return;
while(n%2==0){
printf("2 ");
n=n/2;
}
while(n%3==0){
printf("3 ");
n=n/3;
}
for(int i=5;i*i<=n;i=i+6){
while(n%i==0){
printf("%d\t",i);
n=n/i;
}
while(n%(i+2)==0){
printf("%d\t",(i+2));
n=n/(i+2);
}
}
if(n>3)
printf("%d\t",n);
}
最坏情况 时间复杂度：O（sqrt（n））
评论
nn = n/a;没有效果，因为您下次会立即通过循环进行。n=triangularNumn