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.
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 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.
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.
This only works if you know multiplication tables which is not a given in America these days.
Like the famous Grothendieck prime of course.
Definitely makes me feel better about my own work
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
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.
Except 91.
This is behind a paywall. "A Subscription Is Required to Continue Reading"
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
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.
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
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 :)
/r/whoosh
Nah, the joke just was fairly flat and low-effort.