找出给定数的所有质因数

Question

我要查找all prime factors of a number，例如8: 2 2 2或12: 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 的因子时，它只会多次打印那个因子。

Answer 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;
    }
  }
}

Answer 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

Answer 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))

找出给定数的所有质因数

Find all prime factors of a given number

c

prime-factoring