Panda3D
primeNumberGenerator.cxx
1 // Filename: primeNumberGenerator.cxx
2 // Created by: drose (22Mar01)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #include "primeNumberGenerator.h"
16 
17 
18 ////////////////////////////////////////////////////////////////////
19 // Function: PrimeNumberGenerator::Constructor
20 // Access: Public
21 // Description:
22 ////////////////////////////////////////////////////////////////////
23 PrimeNumberGenerator::
24 PrimeNumberGenerator() {
25  _primes.push_back(2);
26 }
27 
28 ////////////////////////////////////////////////////////////////////
29 // Function: PrimeNumberGenerator::Indexing operator
30 // Access: Public
31 // Description: Returns the nth prime number. this[0] returns 2,
32 // this[1] returns 3; successively larger values of n
33 // return larger prime numbers, up to the largest prime
34 // number that can be represented in an int.
35 ////////////////////////////////////////////////////////////////////
37 operator [] (int n) {
38  nassertr(n >= 0, 0);
39 
40  // Compute the prime numbers between the last-computed prime number
41  // and n.
42  int candidate = _primes.back() + 1;
43  while ((int)_primes.size() <= n) {
44  // Is candidate prime? It is not if any one of the already-found
45  // prime numbers (up to its square root) divides it evenly.
46  bool maybe_prime = true;
47  int j = 0;
48  while (maybe_prime && _primes[j] * _primes[j] <= candidate) {
49  if ((_primes[j] * (candidate / _primes[j])) == candidate) {
50  // This one is not prime.
51  maybe_prime = false;
52  }
53  j++;
54  nassertr(j < (int)_primes.size(), 0);
55  }
56  if (maybe_prime) {
57  // Hey, we found a prime!
58  _primes.push_back(candidate);
59  }
60  candidate++;
61  }
62 
63  return _primes[n];
64 }
int operator[](int n)
Returns the nth prime number.