// SieveImpl.cpp Thu Jan 30 05:45:37 PST 2003 #include"ArrayList.h" #include"LinkList.h" #include"SieveImpl.h" #include SieveImpl::SieveImpl(List * list){ primes = list; } void SieveImpl::insertIfPrime(int n){ if (isPrime(n)) // checking to see if n is prime primes->append(n); // insert n into the list of primes // printf("SieveImpl::insertIfPrime"); } void SieveImpl::print(){ primes->printAll(); } bool SieveImpl::isPrime(int n){ // input condition: primes is a list of all prime numbers less than n bool foundDivisor = false; // we have not found a divisor of n yet bool exceedsSquareRoot = false; // no prime we have seen so far exceeds the square root of n primes->reset(); // we have not visited any prime yet while (primes->hasNext() && !foundDivisor && !exceedsSquareRoot){ // we will terminate the loop if we run out of primes in the list, // or if we find a divisor of n in the list, // or if we visit a prime which is larger than the square root of n int divisor = primes->next(); // divisor will be the smallest prime number not yet tried if (divisor*divisor > n) // checking to see if divisor is greater than the square root of n exceedsSquareRoot = true; else if (n % divisor == 0) // checking to see if divisor divides n foundDivisor = true; } // printf("SieveImpl::insertIfPrime"); // leftover from debugging days return !foundDivisor; // true if we didn't find a divisor, which means n is prime }