Profile image for Alessio Saltarin Guildenstern70
This class computes the first 'n' prime numbers using Eratostene's sieve algorithm.
Language
D
Tags
eratostene primes

Eratostene class in D

1 /** 2 * Eratostene computer 3 * 4 * @example: 5 * 6 // Write first 100 primes 7 8 Eratostene eObj = new Eratostene(100); 9 10 writeln("> Computing primes... "); 11 eObj.crivello(); 12 writeln("> Done. "); 13 14 int[] primes = eObj.primes(); 15 16 for (int j=0; j<primes.length; j++) 17 { 18 writeln(" => " ~ to!string(primes[j])); 19 } 20 21 */ 22 class Eratostene 23 { 24 25 protected int maxval; 26 protected bool sieve[]; 27 28 /** 29 * Constructor 30 * 31 * param maxprime Max Prime 32 */ 33 this(int maxprime) 34 in 35 { 36 assert(maxprime > 1); 37 } 38 body 39 { 40 this.maxval = maxprime; 41 this.sieve = new bool[maxprime]; 42 this.sieve[0..1] = false; 43 this.sieve[2..maxprime] = true; 44 } 45 46 /** 47 * Crivello (sieve) algorithm 48 * 49 */ 50 void crivello() 51 { 52 53 int currPrime = this.nextPrime(0); 54 int i; 55 while (currPrime * currPrime < this.maxval) 56 { 57 i = currPrime * currPrime; 58 while (i < this.maxval) 59 { 60 this.sieve[i] = false; 61 i += currPrime; 62 } 63 currPrime = this.nextPrime(currPrime); 64 } 65 66 } 67 68 /** 69 * Get the sieve 70 * param index Index 71 * 72 */ 73 bool getSieve(int index) pure 74 { 75 return this.sieve[index]; 76 } 77 78 /** 79 * Get the computed prime numbers 80 * return int[] Array of prime numbers 81 * 82 */ 83 int[] primes() pure 84 { 85 int primesLen = this.primesLength(); 86 int[] retPrimes = new int[primesLen]; 87 int j = 0; 88 89 for (int k=0; k < this.maxval; k++) 90 { 91 if (this.sieve[k]) 92 { 93 retPrimes[j++] = k; 94 } 95 } 96 97 return retPrimes; 98 } 99 100 /** 101 * Get the number of primes found. 102 * return The number of primes found 103 */ 104 int primesLength() pure 105 { 106 int primesLen = 0; 107 108 for (int k=0; k < this.maxval; k++) 109 { 110 if (this.sieve[k]) 111 primesLen++; 112 } 113 114 return primesLen; 115 116 } 117 118 119 /** 120 * Return next prime 121 * param lastPrime the last computed prime number 122 */ 123 private int nextPrime(int lastPrime) pure 124 { 125 int nPrime = -1; 126 for (int j=lastPrime+1; j<this.maxval; j++) 127 { 128 if (this.sieve[j]) 129 { 130 nPrime = j; 131 break; 132 } 133 } 134 return nPrime; 135 } 136 137 138 }

Comments