我需要创建一个算法来计算 5 个素数加起来等于 500 的所有组合。 应该有 4088 种组合,但我的代码只生成 3933 种组合,当我删除打破循环的条件时,我得到的组合更少,我不知道为什么。
我有这些说明:
在任何编程语言中,编译一个程序(在算法上,不使用“魔法常量”)找出可以将数字 500 写为五个质数之和的方法的数量。该程序的输出始终是一行找到的组成给定总和的质数,然后是列表下方最后一行找到的组合总数。质数的先后顺序无所谓,只要组合中相同数的位置对调,仍然是同一个结果。 该程序应该是通用的,即当所需的金额发生变化时它也应该是可用的。
我使用了以下代码:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace součet_prv
{
internal class Program
{
static void Main(string[] args)
{
List<string> vysledky= new List<string>();
List<int> prvocisla= new List<int>();
prvocisla = prvocislo();
vysledky = soucet(prvocisla);
vypis(vysledky);
}
static List<int> prvocislo()
{
int x = 500;
List<int> list = new List<int>();
for (int i = 2; i <= x; i++)
{
list.Add(i);
}
for (int i = 2; i <= x; i++)
{
for (int y = i * 2; y <= x; y += i)
{
list.Remove(y);
}
}
return list;
}
static List<string> soucet(List<int>cisla)
{
List<string> list = new List<string>();
int a = 0;
int b = 0;
int c = 0;
int d = 0;
int e = 0;
while (e < cisla.Count)
{
if (cisla[a] + cisla[b] + cisla[c] + cisla[d] + cisla[e] > 500)
{
break;
}
while (d < cisla.Count)
{
if (cisla[a] + cisla[b] + cisla[c] + cisla[d] + cisla[e] > 500)
{
break;
}
while (c < cisla.Count)
{
if (cisla[a] + cisla[b] + cisla[c] + cisla[d] + cisla[e] > 500)
{
break;
}
while (b<cisla.Count)
{
if (cisla[a] + cisla[b] + cisla[c] + cisla[d] + cisla[e] > 500)
{
break;
}
while (a < cisla.Count)
{
if (cisla[a] + cisla[b] + cisla[c] + cisla[d] + cisla[e] > 500)
{
break;
}
if (cisla[a] + cisla[b] + cisla[c] + cisla[d] + cisla[e]==500)
{
list.Add(cisla[a] + "+" + cisla[b] + "+" + cisla[c] + "+" + cisla[d] + "+" + cisla[e] + "= 500");
}
a++;
}
b++;
a = b;
}
c++;
b = c;
}
d++;
c = d;
}
e++;
d = e;
}
return list;
}
static void vypis(List<string> vysledky)
{
using(StreamWriter sw = new StreamWriter("vypis.txt"))
{
for (int i = 0; i < vysledky.Count; i++)
{
sw.WriteLine(vysledky[i]);
}
sw.WriteLine(vysledky.Count);
}
}
}
}
首先,我们可以稍微简化一下问题:因为所有素数都是奇除了
2
then
p0 + p1 + p2 + p3 + p4 == 500
意味着
p2 + p3 + p4 + p5 == 498
在哪里
p0 == 2
。然后我们可以尝试 brute force 其余的 p1, ..., p4
素数。我们得到所有的素数:
private static List<int> Primes(int maxValue) {
List<int> result = new List<int>() { 2 };
for (int number = 3; number <= maxValue; number += 2) {
bool isPrime = true;
foreach (int divisor in result) {
if (number % divisor == 0) {
isPrime = false;
break;
}
if (divisor * divisor > number)
break;
}
if (isPrime)
result.Add(number);
}
return result;
}
然后循环:
int target = 500;
List<int> primes = Primes(target);
for (int i1 = 0; i1 < primes.Count; ++i1)
for (int i2 = i1; i2 < primes.Count; ++i2)
for (int i3 = i2; i3 < primes.Count; ++i3)
for (int i4 = i3; i4 < primes.Count; ++i4)
if (primes[i1] + primes[i2] + primes[i3] + primes[i4] == target - 2)
Console.WriteLine($"2 + {primes[i1]} + {primes[i2]} + {primes[i3]} + {primes[i4]} == {target}");
输出(4088行):
2 + 2 + 2 + 3 + 491 == 500
2 + 2 + 2 + 7 + 487 == 500
2 + 2 + 2 + 31 + 463 == 500
2 + 2 + 2 + 37 + 457 == 500
2 + 2 + 2 + 61 + 433 == 500
2 + 2 + 2 + 73 + 421 == 500
...
2 + 113 + 127 + 127 + 131 == 500
如果你想要 distinct 素数然后修改循环:
int target = 500;
List<int> primes = Primes(target);
for (int i1 = 1; i1 < primes.Count; ++i1)
for (int i2 = i1 + 1; i2 < primes.Count; ++i2)
for (int i3 = i2 + 1; i3 < primes.Count; ++i3)
for (int i4 = i3 + 1; i4 < primes.Count; ++i4)
if (primes[i1] + primes[i2] + primes[i3] + primes[i4] == target - 2)
Console.WriteLine($"2 + {primes[i1]} + {primes[i2]} + {primes[i3]} + {primes[i4]} == {target}");
输出(3611行):
2 + 3 + 5 + 11 + 479 == 500
2 + 3 + 5 + 23 + 467 == 500
2 + 3 + 5 + 29 + 461 == 500
2 + 3 + 5 + 41 + 449 == 500
...
2 + 107 + 113 + 127 + 151 == 500
2 + 109 + 113 + 127 + 149 == 500
2 + 109 + 113 + 137 + 139 == 500
如果你不想改变你的代码。这是你的代码 结果是4088
while (e < cisla.Count)
{
if (cisla[e] > 500)
{
break;
}
d = e
while (d < cisla.Count)
{
if (cisla[d] + cisla[e] > 500)
{
break;
}
c = d
while (c < cisla.Count)
{
if (cisla[c] + cisla[d] + cisla[e] > 500)
{
break;
}
b = c
while (b<cisla.Count)
{
if (cisla[b] + cisla[c] + cisla[d] + cisla[e] > 500)
{
break;
}
a = b
while (a < cisla.Count)
{
if (cisla[a] + cisla[b] + cisla[c] + cisla[d] + cisla[e] > 500)
{
break;
}
if (cisla[a] + cisla[b] + cisla[c] + cisla[d] + cisla[e]==500)
{
list.Add(cisla[a] + "+" + cisla[b] + "+" + cisla[c] + "+" + cisla[d] + "+" + cisla[e] + "= 500");
}
a++;
}
b++;
}
c++;
}
d++;
}
e++;
}