一个正整数能被表示为几个连续素数和的方案C++,C

一些正整数能够表示为一个或多个连续素数的和。例如,整数53有两个表示:53=5+7+11+13+17和53=53;整数41有三个表示:41=2+3+5+7+11+13和41=11+13+17和41=41;整数3只有一个表示,即3=3;整数20没有这样的表示。注意加法操作必须是连续的素数,因此,对于整数20,7+13和3+5+5+7都不是有效的表示。
请编写程序,对于输入的多个整数(在2~10000之间取值,以0结束),给出它们的连续素数和的表示及表示数。要求程序运行结果如下图所示:
《一个正整数能被表示为几个连续素数和的方案C++,C》
思路:首先先把2~10000内的素数取出来。然后用循环条件执行应用,当输入为0的时候退出循环。表达式的输出有多种情况,从于输入的每一个数字,我们从2开始的素数一直加,结果计入sum。当sum大于输入的Num时断开或者当sum=num的时候输出并且count+1,内层循环终止。此次循环结束后从2的后一个素数开始加,,,直到>sum的第一素数,外层循环终止。
我还考虑了一些非法的数据输入。比如当输入数字不符合要求时,让重输,当输入的是其他字母时,清空不合法输入然后重新请求输入num
具体代码如下

/* 输入2~10000之间的数i,以0结束 输出数i由连续的几个素数表示的方案, 输出格式:请输入一个正整数(以0结束):i 组和1,组和2..组和n 共n个方案 */

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

#define MAXSIZE 10000

//计算2~MAXSIZE之间的所有素数并存入数组arr中,返回数组中有效元素的最大下标
void getPrime(vector<int> &arr, int& maxIndex);
//输出方案
void display(const vector<int>& arr,int maxIndex);

int main()
{ 	
	
	vector<int> arr(MAXSIZE, 0);
	int maxIndex;
	getPrime(arr, maxIndex);

	display(arr,maxIndex);
}

void getPrime(vector<int>& arr, int& maxIndex)
{ 
	int count = 0, j;
	for (int i = 2; i <= 10000; i++)
	{ 
		for (j = 2; j <= sqrt(i); j++)
		{ 
			//可以整除,不是素数,终止
			if (i % j == 0)
			{ 
				break;
			}
		}
		//整个循环没有发生break,是素数,存入arr数组中
		if (j > sqrt(i))
		{ 
			arr[count++] = i;
		}
	}
	//记录数组中有多少个素数
	maxIndex = count;
}

void display(const vector<int>& arr, int maxIndex)
{ 
	int num;
	num = MAXSIZE + 2;
	//用while循环实现连续输入
	while (true)
	{ 
		//下一次输入
		cout << "请您输入一个2~" << MAXSIZE << "之间的整数i,以0结束__\b\b";
		cin >> num;

		//当输入非数字时
		while (!cin)
		{ 
			cin.clear();
			while (cin.get() != '\n')
			{ 
				continue;
			}
			cout << "请您输入一个2~" << MAXSIZE << "之间的整数i,以0结束__\b\b";
			cin >> num;
		}

		//输入0时终止
		if (num == 0)
		{ 
			break;
		}

		//数据不合法时的情况
		if (num < 0 || num == 1 || num>MAXSIZE)
		{ 
			cout << "请您输入一个2~" << MAXSIZE << "之间的整数i,以0结束__\b\b";

			cin >> num;
			continue;
		}

		//记录可以拼出来的次数
		int count = 0;
		for (int i = 0; i < maxIndex && arr[i] <= num; i++)	//maxIndex保证采用的都是有效数据,arr[i]<num用于节省时间
		{ 
			//temp记录当前的数据之和与num比较
			int temp = 0;
			for (int j = i; j < maxIndex && arr[j] <= num; j++)
			{ 
				temp += arr[j];
				//拼出来的话就输出一个方案,同时计数+1
				if (temp == num)
				{ 
					for (int z = i; z <= j; z++)
					{ 
						if (z == i)
						{ 
							cout << num << "=" << arr[z];
						}
						else if (z <= j)
						{ 
							cout << "+" << arr[z];
						}
					}
					count++;
					cout << " ";
					
					//每次输出之后将temp置为0,以免影响下次判断
					temp = 0;
				}
				//当当前的连续素数之和已经大于num时,后续都会大于,不能拼成,终止
				if (temp > num)
				{ 
					temp = 0;
					break;
				}
			}
		}
		//输出方案总数,同时将方案数目置为0
		cout << endl << "共" << count << "个方案" << endl << endl;
		count = 0;
	}
}

    原文作者:下坠丷
    原文地址: https://blog.csdn.net/zf111212/article/details/123671124
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞