Skip to content

Instantly share code, notes, and snippets.

@mrmikejones
Created March 13, 2013 14:36
Show Gist options
  • Save mrmikejones/5152714 to your computer and use it in GitHub Desktop.
Save mrmikejones/5152714 to your computer and use it in GitHub Desktop.
Make a list of the prime numbers below a given limit
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeSieve
{
class Program
{
static void Main(string[] args)
{
int number = 0;
Console.WriteLine("Enter Limit...");
string input = Console.ReadLine();
while(!int.TryParse(input, out number))
{
Console.WriteLine("Not a recognised number, try again");
input = Console.ReadLine();
}
List<int> primes = GetPrimes(number);
Console.WriteLine("Primes below {0} are:", number);
primes.ForEach(i => Console.Write("{0}\t", i));
Console.WriteLine("\nPress any key to quit");
Console.ReadLine();
}
public static List<int> GetPrimes(int number)
{
List<int> primes = new List<int>();
if (number < 2) return primes;
Dictionary<int, bool> numberdict = new Dictionary<int, bool>();
for (int i = 3; i < number; i += 2)
{
numberdict[i] = true;
}
primes.Add(2);
int testnumber = 3;
float numbersqrt = (float)Math.Sqrt(number);
while (testnumber < numbersqrt)
{
if (numberdict[testnumber])
{
primes.Add(testnumber);
int multiplier = 2;
while (testnumber * multiplier < number)
{
numberdict[testnumber * multiplier] = false;
multiplier++;
}
}
testnumber += 2;
}
while (testnumber < number)
{
if (numberdict[testnumber])
{
primes.Add(testnumber);
}
testnumber += 2;
}
return primes;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment