Assignment-10 Solution

Description

1. Write a Fortran program which finds a partitions of a set of positive integers into two parts such that the sums of the two parts are as close to each other as possible. For example, if the set is {3,1,4,2,5}, the solution is {3,5} and {1,4,2} or {3,1,4} and {2,5} or {1,2,5} and {3,4}.

Hint: A straightforward approach to the solution checks all possible subsets of the original set of numbers and selects the best solution. The subsets can be determined systematically by binary repre-sentation of consecutive numbers from 1 to 2N − 2; the individual bits in these binary representations indicate the elements which are included in the subset (if the bit is 1) or not (if the bit is 0).

2. The “Sieve of Eratosthenes” is an ancient algorithm for finding prime numbers in a given range. It works efficiently for the smaller primes (below 10 million according to Wikipedia). To find prime numbers less than or equal to a given number N:

1. 1. A list of consecutive integers from 2 to N is created.

1. 2. Let P be equal to 2, the first prime number.

1. 3. All multiples of P, i.e., 2P, 3P, etc. are deleted from the list.

1. 4. The first number greater than P which is left on the list is the next prime number; it replaces P and the steps are repeated from (3).

1. 5. The sieve ends when the next prime number P is greater than ^√N. All numbers left on the list are prime numbers.

Example. Let N = 25. The initial list is:

(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)

For P = 2, after deleting the multiples of 2, the list is:

(2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25)

For P = 3, after deleting the multiples of 3, the list becomes:

(2, 3, 5, 7, 11, 13, 17, 19, 23, 25)

Next P = 5, and after deleting the multiples of 5, the list becomes:

(2, 3, 5, 7, 11, 13, 17, 19, 23)

All numbers remaining on the list are prime.

Write a Fortran program which finds all prime numbers smaller than 5000 using the sieve of Eratos-thenes. Print these numbers 15 per line.

Hint: An integer array A[0:5000], initialized to A[i] = i with A[0] = A[1] = 0, can be used for the sieve. All deleted elements are simply marked as 0 in A. The nonzero elements of A remaining after the sieve are prime numbers.