社区网址：
http://topic.csdn.net/u/20080606/21/49811f8c-39a1-40d8-b8a5-10793bbf18fd.html
我用C#写了一下第一题的解法，可惜在我的机器上运行时间太长了，大家一起探讨一下，看看怎么优化一下。
题目是：
找出满足以下条件的最小素数：
a.3个连续素数的和
b.17个连续素数的和
c.45个连续素数的和
d.979个连续素数的和
e.本身为素数
例如：41为满足以下条件的最小素数：
a.3个连续素数的和（11 ＋ 13 ＋ 17 ＝ 41）
b.6个连续素数的和（2 ＋ 3 ＋ 5 ＋ 7 ＋ 11 ＋ 13 ＝ 41）
我的思路
1、储存一个最小素数min，开始为1，从min开始查找条件d，存入数组1
2、从min开始查找条件c，判断结果，不等于数组1的和时，把数组1的元素2赋值给min，跳转到步骤1；否则继续
3、从min开始查找条件b，判断结果，不等于数组1的和时，把数组1的元素2赋值给min，跳转到步骤1；否则继续
3、从min开始查找条件a，判断结果，不等于数组1的和时，把数组1的元素2赋值给min，跳转到步骤1；否则继续
4、4个连续素数的和出来了，问题解决
好了，帖代码吧：
using System;
using System.Data;
using System.Collections.Generic;
class prime
{
public static void Main(string[] args){
DateTime begin = DateTime.Now; // 开始时间，用于计算整个算法的使用时间
int[] arrCond = {3, 7, 45}; // 条件数组，注意要按从小到大排序，不然会陷入死循环
int primeMin = 1; // 储存查找开始的最小素数
int condLen = arrCond.Length;
List<int>[] arrPrime = PgMain;
// 输出素数数组、数组的和
foreach(List<int> arr in arrPrime)
OutPut(arr);
// 输出整个算法的使用时间
DateTime end = DateTime.Now;
Console.WriteLine(string.Format("共用时：{0}毫秒",(end - begin).TotalMilliseconds));
}
public static List<int>[] PgMain(){
List<int>[] arrPrime = new List<int>[condLen];
while(true){
// 先找最大个素数的数组
arrPrime[condLen - 1] = GetPrimeArr(arrCond[condLen - 1], primeMin);
int resultPrime = CountTotal(arrPrime[condLen - 1]);
for(int loop = condLen - 2; loop >= 0; loop--){
// 取上一个素数数组中最大的作下一个数组的开始条件，优化一点点
int tmp = arrPrime[condLen - 1][arrPrime[condLen - 1].Count-1];
arrPrime[loop] = GetPrimeArr(arrCond[loop], tmp, resultPrime);
if(arrPrime[loop] == null){
primeMin = arrPrime[condLen - 1][1]; // 下一个循环从第二个素数开始查找数组
break;
}
}
if(arrPrime[0] != null)
break;
}
}
// arrLen : 素数数组的长度
// min : 允许的素数的最小值
// 返回值 : 相加也是素数的素数数组
public static List<int> GetPrimeArr(int arrLen, int min){
// 1和2是默认素数，直接添加，后面循环就可以进行 加2 了
List<int> arrPrime = new List<int>();
if(min <= 1){
arrPrime.Add(1);
arrPrime.Add(2);
min = 3;
} else if(min == 2){
arrPrime.Add(2);
min = 3;
} else if(min % 2 == 0) {
min += 1;
}
// 开始无限循环
for(int loop = min; ;loop+=2){
// 长度等于指定的长度时，计算和是否素数，是就退出循环，否就删除最小的素数
if(arrPrime.Count == arrLen){
if(IsPrime(CountTotal(arrPrime)))
break;
else
arrPrime.RemoveAt(0);
}
if(IsOddPrime(loop))
arrPrime.Add(loop);
}
return arrPrime;
}
// arrLen : 素数数组的长度
// min : 允许的素数的最小值
// prime : 素数
// 返回值 : 相加结果等于prime的素数数组
public static List<int> GetPrimeArr(int arrLen, int min, int prime){
List<int> arrPrime;
int primeMinTmp = min;
do{
arrPrime = GetPrimeArr(arrLen, primeMinTmp);
primeMinTmp = arrPrime[1];
} while(CountTotal(arrPrime) < prime);
if(CountTotal(arrPrime) == prime)
return arrPrime;
else
return null;
}
// 判断数字是否素数
public static bool IsPrime(int num){
for(int loop = 2; loop <= Math.Sqrt(num); loop++){
if(num % loop == 0)
return false;
}
return true;
}
// 判断数字是否素数，该数字是大于2的奇数（该方法用于减少循环次数）
public static bool IsOddPrime(int num){
for(int loop = 3; loop <= Math.Sqrt(num); loop+=2){
if(num % loop == 0)
return false;
}
return true;
}
// 对整个数组求和
public static int CountTotal(List<int> arr){
int total = 0;
foreach(int item in arr)
total += item;
return total;
}
// 输出整个数组的求和公式
public static void OutPut(List<int> arr){
string write = string.Empty;
foreach(int loop in arr){
write += " + " + loop;
}
write = write.Substring(3) + " = " + CountTotal(arr) + "/n";
Console.WriteLine(write);
}
}