Hacker News new | past | comments | ask | show | jobs | submit login

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.



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.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: