求出任意合数最多由多少个最小不同质数和组成，并按要求从小到大输出这些质数

浅浅的花香味﹌ 2023-07-22 04:57 11阅读 0赞

## 题目： ##

相约2008：2008是一个合数，求出此合数最多由多少个最小不同质数和组成，并按要求从小到大输出这些质数。

### 分析： ###

（1）质数和合数

合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数

（2）解题思路

本题中数字2008可以是随机一个合数（用n表示），解决本题的关键是找出由最小不同质数之和等于n的数，同时还要求个数是最多的。

我的思路是定义两个数组arr,result。其中arr用来存放2~n的所有质数，count记录质数的个数；result用来存放满足要求的质数。用两个指针i和j指向数组arr，用类似野蛮查找的方法，初始时i=0,j=i+1每当i向后移动一位，j就要将i之后的所有的数从j=i+1位置开始到j=count-1位置结束遍历共count-i次， 若当前求和数sum==n时结束，否则重新计算sum的值，数组result重新保存并且变量j向后移动一位重新计算。用变量num记录每次遍历result数组中个数，最终保留的结果为最大值。  （若文字叙述太绕，可以直接看代码思路应该会比较清晰）

（3）实现步骤

首先，将2~n之间所有的质数保存在一个数组（用数组arr\[\]表示）里面，并且用一个变量（用count表示）记录2~n之间的质数的个数。此处从2~n依次判断，所以是按照从小到大的顺序进行有序存储。

然后，定义两个变量i和j，利用嵌套循环，外层循环用变量i依次指向arr数组从0~count-1的位置，内层循环用变量j依次指向arr数组从i+1~count-1的位置。用变量sum来计算当前质数之和的大小并且用一个新的数组result\[\]来存储质数之和等于n的数。sum每次初始值为arr\[i\],然后在内层循环里面进行计算，此时会出现三种情况：

①当sum<n时，继续进行求和运算sum+=arr\[j\];将当前质数保存在数组result\[\]中并且用变量num记录个数。

②当sum==n时，表示当前已经找出满足要求的数，退出循环输出结果。

③当sum>n时，表明刚才进行的质数求和运算中的数不满足要求，重新进行新一轮运算，此时sum被重新初始化sum=arr\[i\]并且j指向数组arr\[\]的i+k位置，变量num被初始化为1（当num=1时，数组result\[\]就可以重新保存新的值）。k为内层循环重新开始的位置，内层循环每次重新开始时k=k+1向前移动一位数。

因为i,j都是从数组arr\[\]的最低位置开始寻找类似野蛮法，变量i每向后1移动一位，变量j就要将i后面所有的数遍历count-i次来判断是否存在sum==n，所以当出现sum==n这种情况时，数组result\[\]中一定存放的是由最小不同质数之和等于n的数，并且此时质数的个数是最多的。

最后，按序从0~num-1依次输出数组result\[\]中的数即可。

## 代码： ##

void search(int n){
    	int i, j,k,flag,count=0,num=0;
    	int sum = 0;
    	int *arr=(int *)malloc(sizeof(int)*n);
    	int *result = (int *)malloc(sizeof(int)*n);
    	
    	//合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。   质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数
    	//找出2~n之间的质数。
    	for (i = 2; i < n; i++){  
    		flag = 0;
    		for (j = 2; j < i; j++){
                        if (i%j == 0)
                             flag = 1;
    		}
    		if (!flag){
    			arr[count++]=i;  //count记录2~n之间质数的个数 ， 并且将2~n的质数存储在arr数组中
    		}
    	}
    
    	//求出由最小不同质数组成的和为n的最多质数的个数
    	for (i = 0; i < count; i++){
    		sum = arr[i];
    		flag = 0;
    		k = 1;
    		j = i + 1;
    		num = 0;
    		result[num++]=arr[i];
    		while(j < count){
    			if (sum < n){
    				sum += arr[j];
    				result[num++] = arr[j];  //result数组记录合数n由哪些不同质数组成，num记录质数的数量
    				j++;
    			}
    			else if (sum == n){
    				flag = 1;
    				break;
    			}
    			else{
    				k++;
    				j = i + k;
    				sum = arr[i];
    				num = 1;  //若出现sum>n这种情况，表示刚才result数组中存储的不是所要求的数，所以重新记录
    			}
    		}
    		if (flag == 1){//找到sum==n，并且结果保存在result数组中
    			break;
    		}
    	}
    	for (i = 0; i < num; i++)  //输出结果
    		printf("%d ", result[i]);
            printf("\n  %d最多由的%d个不同最小质数组成",n,sum);
    	
    }

## 结果： ##

静态设置的n=2006,输出结果如下：

![20200404234331465.png][]

静态设置的n=2008,输出结果如下：

![2020040423451476.png][]

[20200404234331465.png]: /images/20230528/0073d1d7c9ab47c0ba614f6e6bc1573a.png
[2020040423451476.png]: /images/20230528/baac33ec121e46dcb663bc9681deaec6.png