Skip to content

Instantly share code, notes, and snippets.

@ivanbuhov
Created May 4, 2014 18:45
Show Gist options
  • Save ivanbuhov/6e7f23a4c6b95c1f852c to your computer and use it in GitHub Desktop.
Save ivanbuhov/6e7f23a4c6b95c1f852c to your computer and use it in GitHub Desktop.
Goldbach Conjecture
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace GoldbachConjecture
{
class GoldbachConjecture
{
static void Main()
{
while (true)
{
Console.Write("Enter a number: ");
int number = int.Parse(Console.ReadLine());
IEnumerable<int> result = CalculateGC(number);
Print(number, result);
}
}
// Calculate the Goldbach Conjecture of a number using the standart Eratostene's sieve algorithm
private static IEnumerable<int> CalculateGC(int number)
{
// Validate input
if (number < 4 || number % 2 != 0)
{
throw new ArgumentException("The number must be a positive even integer.", "number");
}
// using BitArray instead of bool[] for memory usage optimization
BitArray sieve = new BitArray(number + 1, true);
sieve[0] = sieve[1] = false;
int step = 2;
List<int> primesInFirstHalf = new List<int>();
primesInFirstHalf.Add(2);
while (step < number)
{
int currentNumber = 2 * step;
while (currentNumber < number)
{
sieve[currentNumber] = false;
currentNumber += step;
}
// Calculate the next step
int oldStep = step;
for (int i = step + 1; i <= number; i++)
{
if (sieve[i])
{
if (i <= number / 2)
{
primesInFirstHalf.Add(i);
}
step = i;
break;
}
}
if (step == oldStep)
{
break;
}
}
// return only these primes which pair number is also prime
return primesInFirstHalf.Where(n => sieve[number - n]);
}
private static void Print(int number, IEnumerable<int> addends)
{
StringBuilder output = new StringBuilder();
output.AppendFormat("{0}", number);
foreach (int addend in addends)
{
output.AppendFormat(" = {0} + {1}", addend, number - addend);
}
Console.WriteLine(output);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment