/** * Assignment 3.a. Prime Numbers * * Compute and print prime numbers using the Sieve of Eratosthenes * and a 1-d array. * * Author: Ron Mak * Department of Computer Engineering * San Jose State University */ #include #include using namespace std; const int MAX_NUMBER = 1000; // maximum possible prime number const int ROW_SIZE = 20; // row size for printing void compute_primes(const int n, bool primes[]); void print_primes(const int n, const bool primes[]); /** * The main: Compute and print the prime numbers up to MAX_NUMBER. */ int main() { bool primes[MAX_NUMBER]; compute_primes(MAX_NUMBER, primes); print_primes(MAX_NUMBER, primes); cout << endl << "Done!" << endl; } /** * Use the Sieve of Eratosthenes to compute a 1-d boolean primes array * where primes[i] is true if i is prime, else primes[i] is false. * @param n the size of the array. * @param primes the boolean primes array. */ void compute_primes(const int n, bool primes[]) { int halfSize = n/2; // the largest possible multiple // Initialize all the vector elements to true. for (int i = 0; i <= n; i++) primes[i] = true; primes[1] = false; // 1 is not prime by definition // Loop over the first half of the vector. for (int i = 2; i <= halfSize; i++) { // For each prime number i, set its multiples m to not prime. if (primes[i]) { for (int m = i + i; m <= n; m += i) primes[m] = false; } } } /** * Print the prime numbers in rows of size ROW_SIZE. * @param primes the boolean primes array. */ void print_primes(const int n, const bool primes[]) { int count = ROW_SIZE; // Loop over all the numbers. for (int number = 1; number < n; number++) { // Print the number only if it's prime. if (primes[number]) { cout << setw(4) << number; count--; // End of row? if (count == 0) { cout << endl; count = ROW_SIZE; } } } if (count != ROW_SIZE) cout << endl; }