## Description

A prime number is a number greater than 1 that has no positive integer divisors

other than 1 and itself. Conversely, a composite number is any number greater than

1 that is divisible by numbers other than 1 and itself. In other words, a composite

number is any number greater than 1 that is not a prime number. To help elucidate

the distinction between these two types of numbers, you will write a program that

accepts as input a positive integer n and outputs a list of all the prime numbers in the

range [2, n] followed by a list of all the composite numbers lying in the same range. To

ensure that your program always terminates within a reasonable amount of time, you

will separate the prime and composite numbers using the Sieve of Eratosthenes.

The Sieve of Eratosthenes is an algorithm designed to efficiently find all prime

numbers less than a given integer limit n. The algorithm indirectly identifies prime

numbers by iteratively marking as composite the multiples of each prime found starting

from the first prime number 2. The steps of the algorithm are enumerated as follows:

1. Create an ordered list l of all integers in the range [2, n].

2. Initialize the first prime number p = 2.

3. Starting from index 2 ∗ p, iterate over the ordered list l in increments of p and

place a mark on each number visited.

4. Find the first unmarked number larger than p in the ordered list l. If no such

number is found, exit the algorithm, otherwise, set p to the unmarked value.

5. If p > b

√

nc, exit the algorithm, otherwise, return to step 3.

An illustrative example of the Sieve of Eratosthenes is provided as follows:

• n = 10

l = [2, 3, 4, 5, 6, 7, 8, 9, 10].

• 1st Iteration:

p = 2 (First prime number)

Iterate and mark in increments of 2.

[2, 3, ✓4, 5, ✓6, 7, ✓8, 9,✟10✟]

• 2nd Iteration:

p = 3 (Next unmarked number larger than 2)

Iterate and mark in increments of 3.

[2, 3, 4✁, 5, ✓6, 7, 8✁, ✓9,✚10] ✚

• 3rd Iteration:

p = 5

5 > b

√

10c so exit algorithm.

1 CS3610

• Final Result:

Prime: [2, 3, 5, 7]

Composite: [4✁, 6✁, 8✁, 9✁,✚10] ✚

Input

A single command line argument containing a positive integer n with the constraints

2 ≤ n ≤ 30000

Output

Using space as a delimiter, print all prime numbers less than or equal to n on one line

followed by all composite numbers less than or equal to n on a separate line. If the

value of n does not lie in the constrained range [2, 30000], output the message Out of

range. If n is not an integer, output the message Nan. If n is not provided as input,

output the message Missing argument.

Sample Test Cases

Test Case 1

$ ./a.out 10

2 3 5 7

4 6 8 9 10

Test Case 2

$ ./a.out

Missing argument

Turn In

Email your source code to yy471014@ohio.edu with the subject “CS3610 Project 1”.

If you have multiple files, package them into a zip file.

Grading

Total: 100 pts.

• 10/100 – Code style, commenting, general readability.

• 05/100 – Compiles.

• 05/100 – Follows provided input and output format.

• 80/100 – Successful implementation of the Sieve of Eratosthenes.

2