c - 质因数分解 + C 中的质数

Question

好吧，我被分配对合数进行素数分解，但问题是我已经硬编码它直到素数:2,3,5,7,11,13,19，我想做到这一点一般。

#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void prime(int flag,int num);
int main()
{
    int num, flag, i, div;
    printf("Enter your number: ");
    scanf("%d", &num);
    flag = 1;
    prime(flag, num);
    printf("Press any key to exit.");
    getchar();
    return 0;
}

void prime(int flag, int num)
{
    void factor(int num, int i);
    int sq, i, square; 
    sq = abs(sqrt(num));

    if (num == 2)
          flag = 1;  
    else
        for (i = 2; i <= sq; i++)
     {
         if (num % i == 0)
         {
             flag = 0;
             break;
         }
         else
             flag = 1;
     }
    if (flag == 1)
        printf("\n%d is a prime number", num);
    else
    {
        printf("\n%d is not a prime number\n", num);
        factor(num, i);
    }
}      

void factor(int num, int i)
{
    for (i = 2; i <= num; i++)
    {
        again:
        if(num % i == 0)
       {
           num = num / i;
           printf("%d x", i);
           if (num != (2||3||5||7||11||17||19))
               goto again;              
       }   
    }
    printf("1\n\n");
}

P.S.:尽量让它尽可能简单。问题出在将它除以最小素数之后。即 2 下一步应该检查该数字是否是素数。如果不是，那么将其因式分解，但我不知道该怎么做。请帮忙。提前谢谢。

Answer 1

在函数中factor ，首先尝试除以2重复，然后尝试每个奇数，同时该奇数的平方小于或等于 num 。当您尝试除以合数时，这个简单的方法有点多余，但由于您已经删除了所有较小的质因数，num不能被这样的合数整除。迭代 while i * i <= num将比您当前的 i <= num 更早停止测试。

尝试编写代码来实现上述算法并将其作为编辑发布。