Hacker News Reader

Comment by danbruc | Hacker News Reader

There are only 1229 primes up to 10,000, not 1230 as the article says. Not sure whether this is a bug in the code or a typo in the article. I still remember this because 25 years ago as a teenager I spend quite some time making primality testing as fast as I could. My implementation was certainly not as naive as the one from the article - only testing up to the square root of n, only testing against primes I had found before - but not sophisticated in any way, for that I lacked the mathematical knowledge. I can not exactly remember how fast I got it but I am pretty sure it was sub-one-second, like 0.2 or 0.3 seconds maybe for the range up to 10,000. On a 50 MHz i486.

View on HN

1 is considered prime by some.

There are also people who consider the world to be flat though. There is a very thorough mathematical definition of prime numbers and 1 is not prime according to that definition.

The definition a prime number is having two factors. As the multiplicative identity, one only has one factor. Some might see primes as being numbers with >=2 factors. This interpretation is less useful. What is completely useless is a definition that makes exclusions of specific numbers as dogma. What does that say about anything? It’s totally arbitrary and unexplanatory.

No, that is not the correct definition of a prime. You can find the right one on Wikipedia.

The reason that 1 is not a prime is to preserve unique factorization. A basic fact from number theory is that every integer uniquely factors as a product of primes, say 21 = 7 times 3. If 1 were a prime, we'd also have 21 = 7 times 3 times 1. That's bad.

In more general number rings, other units (e.g. i) are also not considered primes for the same reason. The exclusion is not arbitrary.

As a complement of your comment: For more information, see Unique Factorization Domains (https://en.wikipedia.org/wiki/Unique_factorization_domain) for the generalization of how prime factorization work on things other than integers.

For a mathematician the suggestion that 1 might be a prime is on a par with a suggestion that a circle is technically a type of triangle.

Whether or not that is true, the code snippet in the article shows this comment:

   #0 and 1 are not primes

That's in the multiprocessing version, which was written by someone else and returns 1229 primes.

The original code includes 1 as a prime.

Reply on news.ycombinator.com