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

int main() {
    long input;
    while (scanf("%ld", &input) != EOF) {
        if (input < 1 || input > 2 * pow(10, 9) + 14) {

            printf("error.\n");
            return 0;
        }
        if (input == 1) {
            break;
        }
        long primeFactor = 2;
        long sqrtinput = sqrt(input);
        while (input != 1) {
            if (input % primeFactor == 0) {
                printf("%ld", primeFactor);
                input /= primeFactor;
                if (input == 1) {
                    break;
                } else {
                    printf(" ");
                }
            } else {
                primeFactor++;
                if(primeFactor > sqrtinput){
                    printf("%ld", input);
                    break;
                }
            }
        }
        printf("\n");
    }
    return 0;
}

​首先看一下题

一、问题分析

分析一下这个问题,首先看描述,发现有一个不是很常见的词汇质因子

先来了解一下质因子

  1. 定义质因子（Prime Factor）又称素因数，是指一个数的因数中为质数的因数。例如，数字 12 的因数有 1、2、3、4、6、12，其中质因数为 2 和 3。
  2. 寻找质因子的方法试除法：这是一种常见的寻找质因子的方法。对于一个给定的正整数n，从最小的质数开始，依次用n除以每个质数p，如果n能被p整除，则p是的n一个质因子，然后将n更新为n/p，继续这个过程，直到n变为1。例如，对于数字36，首先用36/2=18，得到2是一个质因子；接着18/2=9，再用9/3=3，得到2和3都是36的质因子，最后3/3=1，结束。所以36的质因子为2、2、3、3。筛选法（埃拉托斯特尼筛法）：这种方法通常用于找出一定范围内的所有质数，然后再用这些质数去试除给定的数，找出其质因子。首先，列出从2开始的连续自然数，然后从第一个质数2开始，把它的倍数都划掉；接着找到下一个未被划掉的数，它就是下一个质数，再把它的倍数划掉，如此重复，直到所有小于等于给定数平方根的质数都被找到。例如，要找出100以内的质数，首先列出2到100的数字，然后划掉2的倍数（除了2本身），接着找到下一个未被划掉的数3，划掉3的倍数，再找到下一个未被划掉的数5，继续划掉其倍数…… 最后剩下的数字就是质数。然后可以用这些质数去试除给定的数，找出其质因子。
  3. 性质和应用性质：每个大于1的正整数都可以唯一地表示为若干个质因子的乘积，这个性质被称为质因数分解的唯一性（算术基本定理）。例如，60=2*2*3*5。一个数的质因子都是小于或等于这个数本身的质数。应用：在密码学中，质因数分解是一些加密算法的基础，例如 RSA 加密算法就依赖于大整数的质因数分解的困难性。在数学和计算机科学中，质因子分解也被广泛应用于数论、组合数学、图论等领域，以及用于优化算法和解决各种数学问题。

这里要注意一下1不是质数

于是我们得到需求:

1.给定一个整数n,(1 <= n <= 2000000014)

2.计算n的质因子(重复的也要列举)

3.列举的顺序是从小到大

二、解题思路

1.首先我们要把整数读取下来,为此我们需要定义一个能够放得下这个整数的变量,

因为2000000019>2147483647(int的最大值)所以我们需要long来存储这个输入(long的范围-9223372036854775808-9223372036854775807)

2.之后呢我们对这个整数进行处理,

如果是1,则不用输出

如果大于1,则从2开始对这个数字进行整除,如果能被整除,就输出这个数字,然后用得到的商继续整除,如果不能整除,就将我们的除数加1(比如一开始是2,如果不能被2整除就用2+1=3继续整除),直到我们得到商为1的时候证明所有的质因子已经全部输出完毕

三、具体步骤

使用的语言是C

首先#include <stdio.h>引入输入输出库,让我们可以使用fgets来接受数据,printf来输出

然后开始主程序int main(){(写左大括号的时候顺便就把右大括号也打出来,省的忘了)

读取我们的输入使用long input;这里先定义出来

while(scanf("%ld", &input) != EOF) {然后开始读取

做一下验证if(input < 1 || input > 2 * pow(10,9) + 14){

printf("error.\n");

return 0;

}

if(input == 1){

break;

}

接下来定义一个放质因子的变量long pf = 2;

开始整除while(input != 1){这里注意一下能够整除证明余数为0,求余符号是%

if(input % pf == 0){如果可以整除,那么我们要输出质因数,然后将input变成他们的商数

pirntf("%ld",pf);这里注意我们还没有空格,然后还有一点就是input要变成input/pf的商

input/=pf;

if(input == 1){如果此时已经是1了

break;

}else{如果还不是1

printf(" ");

}

} else{如果不能被整除那么我们需要增加我们pf的值

pf++;

}

}

}

别忘了返回return 0;

}

直接提交,发现有一个例子过不去,时间用的太久了

问问豆包,得到了一个答案

原来,如果我们的pf大于input的平方根的时候就可以断定input的质因数是他自己

这是为什么呢?假如我们已经除到了一个质数pf

如果pf大于input的平方根的时候,如果input不是质数,那么他一定可以分解成两个因数a和b(input = a * b)并且,a和b不可能同时大于input的平方根,

举例来说比如input是36(不是质数),那么他可以分解为1 * 36, 2 * 18, 3 * 12, 4 * 9, 6 * 6,在这些组合中没有一组a和b同时大于36的平方根6的也就是说假设我们的

input是1000000007

他的平方根约为31622.8

当我们的pf值为31623的时候,此时就可以确定他的质因数是他自己

用代码表示的话

long sqrtinput = sqrt(input);因为调用了平方根函数sqrt所以前面还需要引入math.h库

if(pf > sqrtinput){

printf("%ld", input);

break;

}

整理一下的话

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

int main(){
    long input;
    while(scanf("%ld", &input) != EOF){
        if(input < 1 || input > 2 * pow(10,9) + 14){
            printf("error.");
            return 0;
        }
        if(input == 1){
            break;
        }
        long primeFactor = 2;
        long sqrtInput = sqrt(input);
        while(input !=1 ){
            if(input % primeFactor == 0){
                printf("%ld", primeFactor);
                input /= primeFactor;
                if(input == 1){
                    break;
                } else{
                    printf(" ");
                }
            }else{
                primeFactor++;
                if(primeFactor > sqrtInput){
                    printf("%ld", input);
                    break;
                }
            }
        }
        printf("\n");
    }
    return 0;
}

感觉有点长因为前面对输入进行了校验​