怎样用C++编写将一个整数分解质因数的程序

//貌似楼上几位都忘了重复测试i能否整除目标整数？

#include <iostream>

using namespace std;

void main()

{

long N,N2,i,t,count;

cout<<"<因式分解>"<<endl;

cout<<"本程序中N和1不视作N的因子。"<<endl;

while(1){

cout<<"请输入一个正整数N:";

cin>>N; N2=N;

count=0; t=N/2; //大于N/2的数不能成为N的因子。（本程序中N本身不算N的一个因子）

for(i=2;i<=t;i++){

if(N%i==0){

if (++count==1) cout<<"N="<<N<<"=";

cout<<i; N/=i;

if(N!=1) cout<<"×";

i--; //再次测试i是否还能成为N的因子

}

if(N==1) break;

}

if(count==0) cout<<N2<<"是质数。"<<endl;

cout<<endl<<endl;

}

}

Private Sub Command1_Click()Dim M As IntegerM = Val(InputBox("输入一个整数:"))Print M & "=";Do While M <> 0For I = 2 To MIf M Mod I = 0 ThenPrint I;M = M \ IExit ForEnd IfNextIf M = 1 Then Exit DoPrint "";LoopEnd Sub从百度百科上抄袭来的。呵呵。另外，上面的程序也可以从2到sqrt(M)来除。没必要到M，因为大于sqrt(M)的，一定有一个小于sqrt(M)的对应。可以省掉一定的运算量。每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。 分解质因数只针对合数Dim x, a, b, k As String Private Sub Command1_Click() a = Val(Text1Text) x = 2 If a <= 1 Or a > Int(a) Then If a = 1 Then Text2Text = "它既不是质数，也不是合数" Else MsgBox "请您先输入数据", vbOKOnly + vbInformation, "友情提示" End If Else Do While a / 2 = Int(a / 2) And a >= 4 If b = 0 Then Text2Text = Text2Text & "2" b = 1 Else Text2Text = Text2Text & "2" End If a = a / 2 k = a Loop Do While a > 1 For x = 3 To Sqr(a) Step 2 Do While a / x = Int(a / x) And a >= x x If b = 0 Then Text2Text = Text2Text & x b = 1 Else Text2Text = Text2Text & "" & x End If a = a / x Loop Next k = a a = 1 Loop If b = 1 Then Text2Text = Text2Text & "" & k Else Text2Text = "这是一个质数" End If End If End Sub Private Sub Command2_Click() Text1Text = "" Text2Text = "" End Sub

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

}

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。

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

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

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

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<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的话可能要自己改下

以上就是关于怎样用C++编写将一个整数分解质因数的程序全部的内容，包括:怎样用C++编写将一个整数分解质因数的程序、求用VB编一个分解质因数的程序、用isprime的C＋＋编写分解质因数的程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！