/** * Assignment 3.c. Prime Spirals * * Use 1- and 2-D vectors to compute and print prime spirals. * A prime spiral consists of consecutive integers starting * at a given value arranged in a growing spiral. Print # * for a prime number and a dot for a nonprime. Patterns * will emerge in the result are in form of diagonal streaks. * * Author: Ron Mak * Department of Computer Engineering * San Jose State University */ #include #include #include using namespace std; const int MAX_START = 50; // maximum starting number void do_prime_spiral(const int n, const int start); void compute_primes(const int n, const int start, vector& primes); void make_spiral(const int n, const int start, const vector& primes, vector>& matrix); void print_spiral(const vector>& matrix); /** * The main: Generate and print prime spirals of various sizes. */ int main() { do_prime_spiral(5, 1); do_prime_spiral(25, 11); do_prime_spiral(35, 0); do_prime_spiral(50, 31); do_prime_spiral(101, 41); } /** * Generate and print a prime spiral of size n with a given starting number. * @param n the size of the square matrix (must be odd and 1 <= n <= MAX_SIZE). * @param start the starting number (1 <= start <= MAX_START). */ void do_prime_spiral(const int n, const int start) { cout << "Prime spiral of size " << n << " starting at " << start << endl; // Make sure that n is odd. if (n%2 != 1) { cout << "***** Error: Size " << n << " must be odd." << endl << endl; return; } // Check that 1 <= start <= MAX_START. if ((start < 1) || (start > MAX_START)) { cout << "***** Error: Starting value " << start << " < 1 or > " << MAX_START << endl << endl; return; } vector primes; vector> matrix; compute_primes(n, start, primes); make_spiral(n, start, primes, matrix); print_spiral(matrix); } /** * Use the Sieve of Eratosthenes to compute a 1-d prime number array * where primes[i] is true if i is prime, else primes[i] is false. * The array must be large enough for an n-by-n prime spiral * with a given starting number. * @param n the size of the prime spiral. * @param start the starting number of the spiral. * @param primes the prime number vector. */ void compute_primes(const int n, const int start, vector& primes) { int stop = n*n + start - 1; // stopping number int halfSize = stop/2; // the largest possible multiple // Initialize all the array elements to true. for (int i = 0; i <= stop; i++) primes.push_back(true); primes[1] = false; // 1 is not prime by definition // Loop over the first half of the array. 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 <= stop; m += i) primes[m] = false; } } } /** * Make a prime spiral in a 2-d square matrix of size n. Start the * spiral with a given starting number. In the spiral, represent * each prime number by '#' and a nonprime number by a dot. * @param n the size square matrix. * @param start the starting number of the spiral. * @param primes the prime number vector. * @param matrix the square matrix that contains the prime spiral. */ void make_spiral(const int n, const int start, const vector& primes, vector>& matrix) { // Initialize the n-by-n matrix to all dots, row by row. // The call matrix.push_back(dot_row) makes a copy of dot_row. vector dot_row; for (int col = 0; col < n; col++) dot_row.push_back('.'); for (int row = 0; row < n; row++) matrix.push_back(dot_row); enum Direction {UP, DOWN, LEFT, RIGHT}; // which way to go int row = n/2; // starting row in the middle int col = row; // starting column in the middle int dr = 0; // row change in a direction int dc = 1; // column change in a direction int steps = 1; // how many steps to take in each direction int stop = n*n + start - 1; // stopping number Direction direction = RIGHT; // starting direction // Loop up to the stopping number. int number = start; while (number <= stop) { // Set values along the current direction step times. for (int j = steps; j > 0; j--) { // Set a '#' if prime. if (primes[number]) matrix[row][col] = '#'; number++; // Move to the next position in the current direction. row += dr; col += dc; } // Change direction. Increase the number of steps // if changing direction to the left or to the right. switch (direction) { case RIGHT: { direction = UP; dr = -1; dc = 0; break; } case DOWN: { direction = RIGHT; dr = 0; dc = 1; steps++; break; } case LEFT: { direction = DOWN; dr = 1; dc = 0; break; } case UP: { direction = LEFT; dr = 0; dc = -1; steps++; break; } } } } /** * Print the square matrix that contains the spiral. * @param matrix the matrix. */ void print_spiral(const vector>& matrix) { cout << endl; for (int row = 0; row < matrix.size(); row++) { for (int col = 0; col < matrix.size(); col++) { cout << matrix[row][col]; } cout << endl; } cout << endl; }