The example given in the article is 2^127 - 1, which was historically proved to be prime without computers using a clever method now known as the Lucas-Lehmer test. Your algorithm is not practical for that number.
The obvious and naive method described above is O(sqrt(N)). For N ~= 2 ^ 127, that is about 2 ^ 64. / The Lucas-Lehmer method described in the article is better (how much better is an exercise for the reader).
Up to 100 it is relatively simple, if you remove the even numbers, the multiples of 3 (summing up their digits recursively gives 3 6 or 9), and those that end at 5, you end up with 25 numbers out of which 22 (88%) are primes. If you further exclude 49 which you should remember is 7^2 from the multiplication table, and 77 that is obviously divisible by 7, you are left with 22/23 chance a number that passes these exclusion criteria is not 91 and hence it is a prime.
The standard divisibility rule for 3, 6 and 9 in base 10 is to sum the digits until you only have one left and check if it's one of those. Here, 5+7=12, 1+2=3, so 57 is divisible by 3.
The HN rule is that anything can be posted if it is accessible to everyone, including via a paywall workaround if it has a paywall that is porous.
The community has converged on this being the least-worst approach after wrestling with the issue for well over a decade, and it's sufficient to helpfully post the archive link with a snarky editorial comment :)
i found out that most articles behind paywalls dont even need the wayback machine to be viewed
if you are using firefox, just enter reading mode and you can read the entire article without popups in your preferred background, text color, font, etc
The original Agrawal, Kayal, Saxena "Primes is in P" paper is actually an amazing effort in clarity https://annals.math.princeton.edu/wp-content/uploads/annals-... .
Just grab some paper, a pen, and check that no number equal or smaller than its square root divides into it evenly.
That is it. That is all. Pish posh.
The example given in the article is 2^127 - 1, which was historically proved to be prime without computers using a clever method now known as the Lucas-Lehmer test. Your algorithm is not practical for that number.
Ah, but I can assure you, it is just that simple.
If a number is not prime, then it is the product of at least two numbers smaller than itself.
If any of them are larger than its square root, all others must be smaller, or their product would be larger than the candidate prime.
Ergo, just check that the candidate is not evenly divisible by any number equal or lower than its square root.
This reasoning holds, independent of scale.
QED. Check mate. Shazam.
Perfect example of how "if the code is compact, it's fast" can be deceiving :)
The obvious and naive method described above is O(sqrt(N)). For N ~= 2 ^ 127, that is about 2 ^ 64. / The Lucas-Lehmer method described in the article is better (how much better is an exercise for the reader).
/r/whoosh
Nah, the joke just was fairly flat and low-effort.
My favourite prime checking algorithm is that for n < 100 if it looks prime, it is prime.
Up to 100 it is relatively simple, if you remove the even numbers, the multiples of 3 (summing up their digits recursively gives 3 6 or 9), and those that end at 5, you end up with 25 numbers out of which 22 (88%) are primes. If you further exclude 49 which you should remember is 7^2 from the multiplication table, and 77 that is obviously divisible by 7, you are left with 22/23 chance a number that passes these exclusion criteria is not 91 and hence it is a prime.
> summing up their digits recursively gives 3 6 or 9
What does this part mean? For example 57.
57 is 3 times 19.
The standard divisibility rule for 3, 6 and 9 in base 10 is to sum the digits until you only have one left and check if it's one of those. Here, 5+7=12, 1+2=3, so 57 is divisible by 3.
Ah I see what is meant by recursively here. Thanks!
5 plus 7 is 12, which of course has a 1 and a 2, the sum of which is 3.
Like the famous Grothendieck prime of course.
Definitely makes me feel better about my own work
The annoying child in me will always remember correcting my freshman math teacher when he needed a prime number and wrote 91 on the chalkboard.
Are there any numbers that don't look prime but are, in fact, prime? [Other than 2, I suppose.]
11, 13, 17 and 19 used to trip me up. And maybe 67
This only works if you know multiplication tables which is not a given in America these days.
"not given" != "not able to learn"
Except 91.
Pay wall.
Imagine browsing the web without an ad blocker.
[flagged]
The scourge of HN submission rules - "you can submit anything and it's up to everyone else to actually be able to access it".
https://archive.is/8R0Fq
The HN rule is that anything can be posted if it is accessible to everyone, including via a paywall workaround if it has a paywall that is porous.
The community has converged on this being the least-worst approach after wrestling with the issue for well over a decade, and it's sufficient to helpfully post the archive link with a snarky editorial comment :)
If I had my 'druthers designing a new link-share/comment system, the visibility (and mirrors or excerpts) for the target would be part of the model.
In other words, an icon showing whatever-wall status, submitter can add an alternate link, etc.
The standard etiquette on HN is not to bother saying that, just post its archive link already.
I guess that's the answer then -- you need a subscription instead of a computer.
i found out that most articles behind paywalls dont even need the wayback machine to be viewed
if you are using firefox, just enter reading mode and you can read the entire article without popups in your preferred background, text color, font, etc