Hacker News Reader

Comment by WWLink | Hacker News Reader

hahahahahahahah :D

I don't think it's possible to have a finite number of primes though? But it's a programming interview, so really, who gives a shit?!

View on HN

Yes, it's not possible to have finite primes. Take all the primes from 2 to N, multiply them together, and add one to get a prime. If there's always another prime, there's infinite primes!

You don't always get a prime. For example, 4! = 2 * 3 * 4 = 24, 24 + 1 = 25, 25 is not prime. The point is that N! + 1 is not divisible by any number from 2 to N (always leaves a remainder of 1), so either it is prime, or it is divisible by something larger than N!, therefore larger than N. In the case of 25, it is divisible by 5 (> 4).

The parent said to multiply _only the primes_ from 2 to N, and then add one not factorial plus one.

In your example it would be (2 * 3) + 1 = 7, prime.

Oh, sorry, didn't realize that. It still doesn't work, though, as the example of 2 * 3 * 5 * 7 * 11 * 13 + 1 = 59 * 509 shows.

It's a little bit more subtle. Assume that there is a finite number of primes, and P is the set of all primes p0, p1, p2... pn. If you multiply all these together and add 1, you have a number Q that's not divisible by any number in P. So P cannot be the set of all primes.

Right, but if you were testing N=13 as the highest prime, then (2 * 3 * 5 * 7 * 11 * 13) + 1 must either be prime itself, i.e. have no prime factors, or must have a prime factor greater than 13. And in either case, a prime greater than 13 exists - in your example, 59.

This is Euclid's proof [1] and it's some 2300 years old.

[1] https://en.wikipedia.org/wiki/Euclid%27s_theorem

Reply on news.ycombinator.com