# Generating Prime Numbers

One algorithm that can be used to check if a number is prime is to simply try dividing it by every integer from 2 to its square root. If the remainder upon each division is not zero, the number is prime. Otherwise, its composite. Another algorithm that accomplishes the same task employs the Sieve of Eratosthenes.

Write a class named PrimeNumberGenerator whose main method prompts the user for some positive integer $n$ and a selection of one of the two aforementioned algorithms to be used. The program should then use the algorithm selected to generate and print all of the primes from 2 to $n$, as shown below, reporting at the conclusion of its run how long in milliseconds all of the calculations took. Is there a more efficient method (i.e., a method that takes less time to execute) for larger values of $n$?

Sample runs:

This program will generate all of the prime numbers from 1 to n
---------------------------------------------------------------
Enter the value of n: 300

Enter '1' to generate them by testing each number's possible divisors,
or '2' to generate them using the Sieve of Eratosthenes: 1

2	3	5	7
11	13	17	19
23	29	31	37
41	43	47	53
59	61	67	71
73	79	83	89
97	101	103	107
109	113	127	131
137	139	149	151
157	163	167	173
179	181	191	193
197	199	211	223
227	229	233	239
241	251	257	263
269	271	277	281
283	293

Generating the list above took 3 milliseconds.

This program will generate all of the prime numbers from 1 to n
---------------------------------------------------------------
Enter the value of n: 100

Enter '1' to generate them by testing each number's possible divisors,
or '2' to generate them using the Sieve of Eratosthenes: 2

2	3	5	7
11	13	17	19
23	29	31	37
41	43	47	53
59	61	67	71
73	79	83	89
97

Generating the list above took 1 millisecond.


Watch the details -- note that when the number of milliseconds equals 1 above, the singular form, "millisecond", is used in the output, while otherwise the plural form, "milliseconds", is used.