## Description

- 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).

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

- A list of consecutive integers from 2 to Nis created.

- Let Pbe equal to 2, the first prime number.

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

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

- The sieve ends when the next prime number Pis 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.