Panda3D

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