英文:
sum of 5 prime numbers equal to 500
问题
我需要创建一个计算所有相加为500的5个质数组合的算法。应该有4088种组合，但我的代码只生成了3933种组合，当我去掉破坏循环的条件时，生成的组合更少，我不知道为什么。
我有以下指令：
在任何编程语言中编写一个程序，用算法方式（不是使用“魔术常数”）找出将数字500写成五个质数之和的方式数量。程序的输出将始终是找到的质数列表，使其总和等于给定的数，然后是列表下方的总找到组合的数量。质数的顺序不重要，只要是相同数字的组合的交换位置，它仍然是同一结果。
该程序应该是通用的，即当所需的总和发生变化时，它也应该是可用的。
我使用了以下代码：（以下是你提供的代码）
英文:
I need to create an algorithm that calculates all combinations of 5 prime numbers that add up to 500.
There should be 4088 combinations but my code generates only 3933 combinations and when I remove the conditions that breaks the cycle I get even less combinations and I don´t know why.
I have these instructions:
In any programming language, compile a program that (algorithmically, not with a "magic constant") finds out the number of ways in which it is possible to write the number 500 as the sum of five prime numbers. The output of the program will always be a line of found prime numbers making up the given sum, followed by the total number of found combinations on the last line below the list. The order of the prime numbers does not matter, as long as there are only swapped positions of the same numbers in the combination, it is still one and the same result.
The program should be universal, i.e. it should also be functional when the required sum is changed.
i used following code:
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);
}
}
}
}
答案1
得分: 2
首先，我们可以稍微简化这个问题：由于所有质数都是奇数，除了2以外，因此
p0 + p1 + p2 + p3 + p4 == 500
意味着
p2 + p3 + p4 + p5 == 498
其中p0 == 2。然后，我们可以尝试对剩下的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) {
var (q, r) = int.DivRem(number, divisor);
if (r == 0) {
isPrime = false;
break;
}
if (q < divisor)
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
如果您想要不同的质数，那么可以修改循环：
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
英文:
First of all, we can slightly simplify the problem: since all primes are odd except for 2 then
p0 + p1 + p2 + p3 + p4 == 500
means
p2 + p3 + p4 + p5 == 498
where p0 == 2. Then we can try brute force for the rest p1, ..., p4 primes. We obtain all the prime numbers:
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) {
var (q, r) = int.DivRem(number, divisor);
if (r == 0) {
isPrime = false;
break;
}
if (q < divisor)
break;
}
if (isPrime)
result.Add(number);
}
return result;
}
And loop:
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}");
Output (4088 lines):
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
If you want distinct primes then modify the loops:
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}");
Output (3611 lines):
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
答案2
得分: 0
如果您不想更改您的代码。以下是您的代码，结果为 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++;
}
注意：我已经忽略了代码部分，只翻译了注释和字符串。
英文:
If you don't want to change your code. Here is your code
And result is 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++;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论