c语言分解质数

首先你的if语句写错了,我想你的意思是if(i==n)吧，不是把n的值赋给i，如果照你这么写的话，第一个只输出1个n的值，第二个输出的会有n-1个n的值。如果按照if（i==n）来写的话，放在for里面和放到for外面其实没什么区别。

#include <stdioh>

#include <mathh>

int isPrime(int n) { // n是质数返回1，否则返回0

int flag = 1; // 标志

if(n < 2) return 0; // 质数大于1

for(int i = 2; i <= sqrt(n) && flag; ++i) {

if(n % i == 0) flag = 0; // 能整除，就不是质数

}

return flag;

}

int main() {

int n,an,flag;

while(1) {

printf("输入一个整数(0 -- 65535):");

if(scanf("%d",&n) != 1 || n < 0 || n > 65535) {

printf("数据错误。\n");

fflush(stdin); // 刷新键盘输入缓冲区用以清除非数字字符响应scanf("%d",&n)

continue;

}

printf("%d = ",n);

flag = 1; // 输出格式控制标志

for(int i = 2; i <= n; ++i) {

if(n % i == 0 && isPrime(i)) {

if(flag) { // 第一个质因子的输出格式

printf("%d",i);

flag = false;

}

else printf("  %d",i); // 其他质因子的输出格式

n /= i; // 剔除已经求得的质因子

--i; // 应对相同质因子

}

}

printf("\n1、继续，0、结束:");

scanf("%d",&an);

if(an == 0) break;

}

return 0;

}

将一个正整数分解质因数。例如:输入60；打印出2352

算法实现构思:

1、用Scanner实现输入一个正整数n

2、用一个for循环遍历一个从 k=2开始查找到k<=n的数

3、如果 n%k==0的时候，输出k的值

4、然后把n的值递归一下，即 n=n/k

5、这个时候要把for循环重新执行，即再定义k=2

下面是实现代码：

下面是运行结果

上面是后来整理的构思以及代码实现，一开始拿到这个题目，就立马去做了，可是马上掉进了各种各样的坑，我觉得以后做算法题先把做题思路想好，从部分到整体，不然一道简单的算法题就要耗掉很多时间。

参考资料

CSDNCSDN[引用时间2018-1-5]

如何分解质数

如何分解质因数

短除法

求最大公约数的一种方法，也可用来求最小公倍数。

求几个数最大公约数的方法，开始时用观察比较的方法，即：

先把每个数的约数找出来，然后再找出公约数，最后在公约数中找出最大公约数。

例如：求12与18的最大公约数。

12的约数有：1、2、3、4、6、12。

18的约数有：1、2、3、6、9、18。

12与18的公约数有：1、2、3、6。

12与18的最大公约数是6。

这种方法对求两个以上数的最大公因数，特别是数目较大的数，显然是不方便的。于是又采用了给每个数分别分解质因数的方法。

12＝2×2×3

18＝2×3×3

12与18都可以分成几种形式不同的乘积，但分成质因数连乘积就只有以上一种，而且不能再分解了。所分出的质因数无疑都能整除原数，因此这些质因数也都是原数的约数。

从分解的结果看，12与18都有公约数2和3，而它们的乘积2×3＝6，就是 12与18的最大公约数。

采用分解质因数的方法，也是采用短除的形式，只不过是分别短除，然后再找公约数和最大公约数。如果把这两个数合在一起短除，则更容易找出公约数和最大公约数。

从短除中不难看出，12与18都有公约数2和3，它们的乘积2×3＝6就是12与18的最大公约数。与前边分别分解质因数相比较，可以发现：不仅结果相同，而且短除法竖式左边就是这两个数的公共质因数，而两个数的最大公约数，就是这两个数的公共质因数的连乘积。

以上就是关于c语言分解质数全部的内容，包括:c语言分解质数、用isprime的C＋＋编写分解质因数的程序、用java编程 将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！