Reference no: EM131788464

Write a program for the Peter-the-postman problem in Problem 3, but use a dynamically allocated array

A prime number is an integer greater than 1 whose only positive divisors are 1 and the integer itself. The Greek mathematician Eratosthenes developed an algorithm, known as the Sieve of Eratosthenes, for finding all prime numbers less than or equal to a given number n-that is, all primes in the range 2 through n. Consider the list of numbers from 2 through n. Two is the first prime number, but the multiples of 2 (4,6,8, ...) are not, and so they are crossed out in the list. The first number after 2 that was not crossed out is 3, the next prime. We then cross out from the list all higher multiples of 3 (6,9,12, ...). The next number not crossed out is 5, the next prime, and so we cross out all higher multiples of 5 (10, 15,20, ...). We repeat this procedure until we reach the first number in the list that has not been crossed out and whose square is greater than n. All the numbers that remain in the list are the primes from 2 through n. Write a program that uses this sieve method and an array to find all the prime numbers from 2 through n. Execute the program for n =550 and for n =5500.