Problem Statement
A prime number is a number whose only divisors are 1 and itself. A sublinear polynomial-time algorithm has been shown to exist that determines primality or non-primality with certainty, unlike the previous probablistic tests, but it is extremely complicated. There must be an easier way.
In engineering, exact solutions are often not required, only good approximations. Thus, an "Engineer's Prime" of order N is any number that is divisible by none of the first N primes, since the smallest primes are easy to remember: 2, 3, 5, and so on. Note that 1 is not considered a prime in this case.
Given an int N, your method should return the smallest Engineer's Prime of order N that is not prime.
Definition
- Class:
- EngineersPrimes
- Method:
- smallestNonPrime
- Parameters:
- int
- Returns:
- long
- Method signature:
- long smallestNonPrime(int N)
- (be sure your method is public)
Notes
- 1 is not to be considered prime.
Constraints
- N will be between 1 and 100000, inclusive.
Examples
3
Returns: 49
The first three primes are 2, 3, and 5. Next, look through the numbers after 5 that are not divisible by any of those first three primes. These are, in order, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, and 49, all of which are prime except the last.
1
Returns: 9
The first odd number that is not prime.
265
Returns: 2886601
1835
Returns: 247716121
4000
Returns: 1431184561
3417
Returns: 1010794849
2
Returns: 25
4
Returns: 121
5
Returns: 169
50
Returns: 54289
300
Returns: 3972049
3000
Returns: 753886849
2000
Returns: 302516449
1000
Returns: 62837329
3999
Returns: 1429822969
3998
Returns: 1429671721
688
Returns: 26739241
2460
Returns: 482285521
3990
Returns: 1420611481
10000
Returns: 10971096049
100000
Returns: 1689274677841
15048
Returns: 27019798129
33912
Returns: 160577319841
95899
Returns: 1543013636761
99999
Returns: 1689243484681
46001
Returns: 312591691801
65536
Returns: 675103792609
153
Returns: 786769
10000
Returns: 10971096049
100000
Returns: 1689274677841
1
Returns: 9
98999
Returns: 1652553957289