00001 // Filename: primeNumberGenerator.cxx 00002 // Created by: drose (22Mar01) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "primeNumberGenerator.h" 00016 00017 00018 //////////////////////////////////////////////////////////////////// 00019 // Function: PrimeNumberGenerator::Constructor 00020 // Access: Public 00021 // Description: 00022 //////////////////////////////////////////////////////////////////// 00023 PrimeNumberGenerator:: 00024 PrimeNumberGenerator() { 00025 _primes.push_back(2); 00026 } 00027 00028 //////////////////////////////////////////////////////////////////// 00029 // Function: PrimeNumberGenerator::Indexing operator 00030 // Access: Public 00031 // Description: Returns the nth prime number. this[0] returns 2, 00032 // this[1] returns 3; successively larger values of n 00033 // return larger prime numbers, up to the largest prime 00034 // number that can be represented in an int. 00035 //////////////////////////////////////////////////////////////////// 00036 int PrimeNumberGenerator:: 00037 operator [] (int n) { 00038 nassertr(n >= 0, 0); 00039 00040 // Compute the prime numbers between the last-computed prime number 00041 // and n. 00042 int candidate = _primes.back() + 1; 00043 while ((int)_primes.size() <= n) { 00044 // Is candidate prime? It is not if any one of the already-found 00045 // prime numbers (up to its square root) divides it evenly. 00046 bool maybe_prime = true; 00047 int j = 0; 00048 while (maybe_prime && _primes[j] * _primes[j] <= candidate) { 00049 if ((_primes[j] * (candidate / _primes[j])) == candidate) { 00050 // This one is not prime. 00051 maybe_prime = false; 00052 } 00053 j++; 00054 nassertr(j < (int)_primes.size(), 0); 00055 } 00056 if (maybe_prime) { 00057 // Hey, we found a prime! 00058 _primes.push_back(candidate); 00059 } 00060 candidate++; 00061 } 00062 00063 return _primes[n]; 00064 }