fork(2) download
copy 
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Diagnostics;
  5.  
  6. public class PrimeList
  7. {
  8. 	// A list of prime values.
  9. 	private static readonly List<int> Primes        = new List<int>( 10001 );
  10.  
  11. 	// An array of bits indicating whether the odd numbers (from 3 upwards)
  12. 	// are prime (true) or non-prime (false).
  13. 	private static readonly BitArray  OddPrimeSieve = new BitArray( 100000,
  14. 	               													true );
  15.  
  16. 	// The maximum prime number that has currently been found from the sieve.
  17. 	private static          int       MaxSieved     = 3;
  18.  
  19. 	static PrimeList()
  20. 	{
  21. 		Primes.Add( 2 );
  22. 		Primes.Add( 3 );
  23. 	}
  24.  
  25. 	public static int GetNthPrime( int index )
  26. 	{
  27. 		// Caclulate the sieve index of the currently maximum sieved prime.
  28.     	int sieveIndex = ( MaxSieved - 3 ) / 2;
  29.     	int multiple;
  30.  
  31. 		while( Primes.Count < index )
  32. 		{
  33. 			// Set all higher multiples of the current prime to be non-prime.
  34. 	        for ( multiple = sieveIndex + MaxSieved;
  35. 	        		multiple < OddPrimeSieve.Count; 
  36. 	        		multiple += MaxSieved )
  37.     		{
  38. 	            OddPrimeSieve.Set( multiple, false );
  39.     		}
  40.  
  41. 	        // Find the sieve index of the next prime number.
  42. 	        do
  43. 	        {
  44. 	        	++sieveIndex;
  45. 	        }
  46. 	        while ( sieveIndex < OddPrimeSieve.Count
  47. 	        		&& !OddPrimeSieve[sieveIndex] );
  48.  
  49. 			// Reverse the calculation of the sieve index to get the next prime.
  50. 	        MaxSieved = 2*sieveIndex + 3;
  51.  
  52. 	        // Add the prime to the list.
  53. 		    Primes.Add( MaxSieved );
  54. 		}
  55. 		return Primes[index-1];
  56. 	}
  57.  
  58. 	public static void Main()
  59. 	{
  60. 		Stopwatch sw = new Stopwatch();
  61. 		sw.Start();
  62. 		int p = GetNthPrime(10001);
  63. 		sw.Stop();
  64. 		Console.WriteLine( p );
  65. 		Console.WriteLine( "Time to calculate in milliseconds : {0}",
  66. 							sw.ElapsedMilliseconds );
  67. 	}
  68. }
Success #stdin #stdout 0.06s 25080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
104743
Time to calculate in milliseconds : 4
https://ideone.com/DySeVe
language:
C# (gmcs 5.20.1)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!