分解质因数的方法

1、相乘法

写成几个质数相乘的形式（这些不重复的质数即为质因数），实际运算时可采用逐步分解的方式。

如：36=2233 运算时可逐步分解写成36=49=2233或312=3223

2、短除法

从最小的质数除起，一直除到结果为质数为止。分解质因数的算式的叫短除法。

扩展资料：

定理

不存在最大质数的证明：（使用反证法）

假设存在最大的质数为N，则所有的质数序列为：N1，N2，N3……N

设M=（N1×N2×N3×N4×……N）+1，

可以证明M不能被任何质数整除，得出M也是一个质数。

而M>N，与假设矛盾，故可证明不存在最大的质数。

最大公约数的求法：

1、用分解质因数的方法，把公有的质因数相乘。

2、用短除法的形式求两个数的最大公约数。

3、特殊情况：如果两个数互质，它们的最大公约数是1。

如果两个数中较小的数是较大的数的约数，那么较小的数就是这两个数的最大公约数。

参考资料来源：百度百科——分解质因数

public class Test {

/

@param args

/

public static void main(String[] args) {

// TODO Auto-generated method stub

int num=40;//测试数据，你也可以用Scanner获取输入数据，但是为了方便

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

while(num!=i){

if(num%i==0){

Systemoutprintln("质因数是："+i);

num=num/i;

}

else

break;

}

}

Systemoutprintln("质因数是："+num);

}

}

#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;

}

#include<iostreamh>

//递归可以么

int f(int n, int i=1)

{

if(i==1)

{

cout<<n<<"=";

f(n,2);

}

else if(ii>n)cout<<n;

else if(n%i==0)

{

cout<<i<<"";

f(n/i,i);

}

else f(n,i+1);

}

void main()

{

int n;

cin>>n;

f(n);

}

//vc6的程序,如果不是用vc6的话可能要自己改下

将一个正整数分解质因数。例如:输入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]

题目：将一个正整数分解质因数。例如：输入90,打印出90=2 3 35。

正解：

1使用该数m去除以2到sqrt(m)之间的数，如果不能够整除的话，说明其本身就是质数了。

2使用该数m去除以2到sqrt(m)之间的数，如果能够整除的话，再继续循环，直到回到第一步为止。

整数i初始为2，。。。直到sqrt(num)

8

8/2=4

4/2=2

2/2=1

所以8的质因数为2 2 2

9

9/2！=0 i++;

9/3=3

3/3=1

所以9的质因数为33

27

27/2!=0 i++

27/3=9

9/3=3

3/3=1

所以27的质因数为3 3 3

100

100/2=50

50/2=25

25/2！=0 i++

25%3!=0 i++

25%4!=0 i++

25%5=0 25/5=5

5%5=0 5/5=1

所以100的质因数为2 2 55

90

90%2=0 90/2=45

45%2!=0 所以i++

45%3=0 45/3=15

15%3=0 15/3=5

5%3!=0 i++

5%4!=0 i++

5%5=0 5/5=1

所以90的质因素为2 3 35

public void zhiyinshu(int num){

int i=2;

int shang;

while(num!i=1){

if(num%i==0){

num=num/i;

print(i+"");

}else{

i++;

}

}

}

以上就是关于分解质因数的方法全部的内容，包括:分解质因数的方法、急！！JAVA程序 怎么把一个数分解质因数呀要代码、用isprime的C＋＋编写分解质因数的程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！