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);
}
}
}
}
>Solution :
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) {
if (number % divisor == 0) {
isPrime = false;
break;
}
if (divisor * divisor > number)
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