题解 | #质数因子#
质数因子
https://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607
#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;
}
首先看一下题
一、问题分析
分析一下这个问题,首先看描述,发现有一个不是很常见的词汇质因子
先来了解一下质因子
- 定义质因子（Prime Factor）又称素因数，是指一个数的因数中为质数的因数。例如，数字 12 的因数有 1、2、3、4、6、12，其中质因数为 2 和 3。
- 寻找质因子的方法试除法：这是一种常见的寻找质因子的方法。对于一个给定的正整数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，继续划掉其倍数…… 最后剩下的数字就是质数。然后可以用这些质数去试除给定的数，找出其质因子。
- 性质和应用性质：每个大于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;
}
感觉有点长因为前面对输入进行了校验
字节跳动公司氛围 556人发布
