【经典100题】题目14 将一个正整数分解质因数

分手后的思念是犯贱 2022-04-05 05:56 200阅读 0赞

# C语言实现 #

#include<stdio.h>
    
    void main()
    {
    	int num, n, i, j, t;
    	int k = 2;
    	int f[10] = { 0 };
    	int index = 0;
    	printf("请输入一个正整数：");
    	scanf("%d", &num);
    	n = num;
    	for (j = 1; j < (int)(num / 2) + 1; j++)
    	{
    		for (i = k; i <= n; i++)
    		{
    			t = n%i;
    			if (t == 0) //判断能否被i整除
    			{
    				f[index] = i;
    				n = (int)(n / i);
    				index++;
    				break;
    			}
    			else
    				k++;
    		}
    	}
    	if (f[0] == 0)
    		printf("没有质因数\n");
    	else
    	{
    		f[index + 1] = n;
    		printf("%d = %d", num, f[0]);
    		for (int i = 1; i < sizeof(f) / sizeof(f[0]); i++)
    		{
    			if (f[i] == 0)//初始化的数组后面是0，不再输出
    				break;
    			printf("*%d", f[i]);
    		}
    	}
    }

运行结果：

> 请输入一个正整数：1234  
> 1234 = 2\*617请按任意键继续. . .

--------------------

# C++语言实现 #

#include<iostream>
    #include<vector>
     
    using namespace std;
     
    void main()
    {
    	int num, n, i, j,t;
    	int k = 2;
    	vector<int> v1;
    	int size;
    	cout << "请输入一个正整数" << endl;
    	scanf("%d", &num);
    	n = num;	
    	for (j = 1; j < int(num/2) + 1; j++)
    	{
    		for (i = k; i < n; i++)
    		{
    			t = n%i;
    			if (t == 0)
    			{
    				v1.push_back(i);
    				n = int(n/i);
    				break;
    			}
    			else
    				k++;			
    		}
    	}
    
    	size = v1.size();
    	if (size==0)
    		cout << "没有质因数" << endl;	
    	else
    	{
    		v1.push_back(n);
    		cout <<num<<"="<<v1[0];
    		for (int i = 1; i < size+1; i++)
    			cout << "*"<<v1[i] ;		
    	}	
    }

运行结果：

> 请输入一个正整数  
> 1234  
> 1234=2\*617请按任意键继续. . .

--------------------

# python语言实现 #

n = num = int(input('请输入一个数字：'))  #用num保留初始值
    f = []  #存放质因数的列表
    k = 2
    
    for j in range(int(num/2)+1):  #判断次数仅需该数字的一半多1次
        for i in range(k, n):
            t = n % i  #i不能是n本身
            if t == 0:  #若能整除
                f.append(i)  #则表示i是质因数
                n = n//i  #除以质因数后的n重新进入判断，注意应用两个除号，使n保持整数
                break  #找到1个质因数后马上break，防止非质数却可以整除的数字进入质因数列表
            else:
                k = k+1 #如果i不是质因数，下一次循环就从k+1开始
            
    if len(f) == 0:  #若一个质因数也没有
        print('该数字没有任何质因数。')
    else:  #若至少有一个质因数
        f.append(n)  #此时n已被某个质因数整除过，最后一个n也是其中一个质因数
        f.sort()  #排下序
        print('%d=%d' % (num, f[0]), end='')
        for i in range(1,len(f)):
            print('*%d' % f[i], end='')

运行结果：

> 请输入一个数字：1234  
> 1234=2\*617  
> >>>

--------------------

★finished by songpl,2018.12.12