Panda3D

primeNumberGenerator.cxx

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 }
 All Classes Functions Variables Enumerations