Smipple is shutting down Nov 30, 2017. Some features are currently disabled.
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