C程序实现整数的素数和分解问题

Rowena ·

更新时间:2024-09-21

· 910 次阅读

本文以实例形式讲述了C程序实现整数的素数和分解问题，分享给大家供大家参考之用。具体方法如下：

要求：对于一个给定的整数，输出所有这种素数的和分解式，对于同构的分解只输出一次(比如5只有一个分解2+3，而3+2是2+3的同构分解式)。

例如：

对于整数8，可以作为如下三种分解：
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5

看到此题时，我的头一反应是求解背包问题

思路如下：

f(N, array) = f(N - array[i], array), 保存结果，array是保存里面元素值，即所有素数，参考前面一题，如果素数只能唯一使用一次，那么就建立对应的一个bool数组即可，每使用一次就标记为true，然后递归函数之后需要重新置为false，对于本题不需要如此，但是需要将保存结果的数组除去当前尝试的素数。

代码如下：


/*  
* Copyright (c) 2011 alexingcool. All Rights Reserved.  
*/ 
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> result;
vector<int> prvec;
void outputResult(int N, vector<int> &prime, vector<int> &result)
{
 if(N < 0)
 return;
 if(N == 0) {
 copy(result.begin(), result.end(), ostream_iterator<int>(cout, " "));
 cout << endl;
 return;
 }
 for(int i = 0; i < prime.size(); i++) {
 //为提高效率，可以在此做个判定条件，尽快返回
 if(N - prime[i] < 0)
  break;
 result.push_back(prime[i]);
 outputResult(N - prime[i], prime, result);
 result.pop_back();
 }
}
void outputResult2(int N, vector<int> &prime, vector<int> &result, int position)
{
 if(N < 0)
 return;
 if(N == 0) {
 copy(result.begin(), result.end(), ostream_iterator<int>(cout, " "));
 cout << endl;
 return;
 }
 for(int i = position; i < prime.size(); i++) {
 //为提高效率，可以在此做个判定条件，尽快返回
 if(N - prime[i] < 0)
  break;
 result.push_back(prime[i]);
 outputResult2(N - prime[i], prime, result, i);
 result.pop_back();
 }
}
bool isPrime(int number)
{
 if(number <= 1)
 return false;
 if(number == 2)
 return true;
 for(int i = 2; i < number; i++) {
 if(number % i == 0)
  return false;
 }
 return true;
}
void generatePrime(int number, vector<int> &result)
{
 for(int i = 2; i < number - 1; i++) {
 if(isPrime(i))
  result.push_back(i);
 }
}
void main()
{
 int number = 8;
 generatePrime(number, prvec);
 outputResult(number, prvec, result);
 cout << "除去同构" << endl;
 outputResult2(number, prvec, result, 0);
}

运行结果如下图所示：

注意：对于同构问题，我是看输出结果之后想到的，outputResult函数中，结果332，这样不对的结果，一个明显的特征是出现3后，其后面的数不能再小于3，那么只需要对保存3当前的position即可，然后在当前position循环，就可以消除同构问题。

相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。

您可能感兴趣的文章:C++实现判断字符串是否回文实例解析C语言判断回文数的小例子C语言实现的统计素数并求和代码分享使用c语言判断100以内素数的示例(c语言求素数)c语言判断是否素数程序代码C++求四个正整数最大公约数的方法C++使用递归方法求n阶勒让德多项式完整实例C++归并排序算法实例C++选择排序算法实例C++冒泡排序算法实例C++插入排序算法实例C++实现N个骰子的点数算法C++实现查找中位数的O(N)算法和Kmin算法C++回文数及素数问题计算方法

c程序素数

1024 个赞