Skip to content

Instantly share code, notes, and snippets.

@AndrewBarfield
Created April 30, 2012 10:45
Show Gist options
  • Save AndrewBarfield/2557312 to your computer and use it in GitHub Desktop.
Save AndrewBarfield/2557312 to your computer and use it in GitHub Desktop.
C#: Calculating prime numbers using the Standard (Naive) Method
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace StandardMethod
{
class Program
{
static void Main(string[] args)
{
DateTime dtStart = DateTime.Now;
GeneratePrimesNaive( 1000000 );
Console.WriteLine( DateTime.Now - dtStart );
Console.Read();
}
public static List<int> GeneratePrimesNaive(int n)
{
List<int> primes = new List<int>();
primes.Add( 2 );
int nextPrime = 3;
while ( primes.Count < n )
{
int sqrt = (int)Math.Sqrt( nextPrime );
bool isPrime = true;
for ( int i = 0 ; (int)primes[i] <= sqrt ; i++ )
{
if ( nextPrime % primes[i] == 0 )
{
isPrime = false;
break;
}
}
if ( isPrime )
{
primes.Add( nextPrime );
}
nextPrime += 2;
}
return primes;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment