UNKNOWN //************************************** // Name: Sieve Of Atkin // Description:Method to implement the <a href="http://en.wikipedia.org/wiki/Sieve_of_Atkin">Sieve of Atkin</a> for finding Prime Numbers. Arguments: int limit Returns: int [ ] // By: Munkyeetr // // // Inputs:None // // Returns:None // //Assumes:None // //Side Effects:None //This code is copyrighted and has limited warranties. //Please see http://www.Planet-Source-Code.com/xq/ASP/txtCodeId.9075/lngWId.10/qx/vb/scripts/ShowCode.htm //for details. //************************************** public static int[] AtkinSieve(int limit) { double root = Math.Ceiling(Math.Sqrt(limit)); bool[] sieve = new bool[limit]; int[] primes = new int[2]; int insert = 3; primes[0] = 2; primes[1] = 3; // initialize sieve to false for (int z = 0; z < limit; z++) { sieve[z] = false; } // main part of atkin sieve for (int x = 1; x <= root; x++) { int xx = (x * x); for (int y = 1; y <= root; y++) { int yy = (y * y); int n = (4 * xx) + (yy); if ((n <= limit) && ((n % 12 == 1) || (n % 12 == 5))) { sieve[n] = !sieve[n]; } n = (3 * xx) + (yy); if ((n <= limit) && (n % 12 == 7)) { sieve[n] = !sieve[n]; } n = (3 * xx) - (yy); if ((x > y) && (n <= limit) && (n % 12 == 11)) { sieve[n] = !sieve[n]; } } } // loop through sieve and remove squares of primes for (int r = 5; r <= root; r++) { int rr = (r * r); if (sieve[r]) { for (int i = rr; i < limit; i += rr) { sieve[i] = false; } } } // loop through sieve and add primes for return for (int a = 5; a < limit; a++) { if (sieve[a]) { Array.Resize(ref primes, insert); primes[insert - 1] = a; insert++; } } return primes; }