3 ms·
My favourite prime checking algorithm is that for n < 100 if it looks prime, it is prime.
by IsTom 11mo ago
My favourite prime checking algorithm is that for n < 100 if it looks prime, it is prime.
- throwaway81523 11mo agoLike the famous Grothendieck prime of course.
- xorbax 11mo agoDefinitely makes me feel better about my own work
- emaccumber 11mo agoThe annoying child in me will always remember correcting my freshman math teacher when he needed a prime number and wrote 91 on the chalkboard.
- deleted 11mo ago[deleted]
- GMoromisato 11mo agoAre there any numbers that don't look prime but are, in fact, prime? [Other than 2, I suppose.]
- andruby 11mo ago11, 13, 17 and 19 used to trip me up. And maybe 67
- mootothemax 11mo ago67 has absolutely no right to be prime. Sitting there looking all innocent.
- bombcar 11mo agoMaybe that’s the real secret behind the 6-7 meme going around
- ridiculous_fish 11mo agoExcept 91.
- conradev 11mo agoThis only works if you know multiplication tables which is not a given in America these days.
- gosub100 11mo ago"not given" != "not able to learn"
- freehorse 11mo agoUp 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.
- jeffbee 11mo ago> summing up their digits recursively gives 3 6 or 9 What does this part mean? For example 57.
- hollerith 11mo ago5 plus 7 is 12, which of course has a 1 and a 2, the sum of which is 3.
- zdimension 11mo ago57 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.
- jeffbee 11mo agoAh I see what is meant by recursively here. Thanks!
- squigz 11mo agoMath is not my strong suit at all, so I probably won't grok this, but that kind of blows my mind, so I'm curious... how?! That works for any arbitrarily large number? Math is crazy!... still don't want to study it though!
- moring 11mo agoYes. A number like 123456 = 1 * 100000 + 2 * 10000 + 3 * 1000 + 4 * 100 + 5 * 10 + 6 = 1 * (99999+1) + 2 * (9999+1) + 3 * (999+1) + 4 * (99+1) + 5 * (9+1) + 6 When checking whether it is a multiple of some k, you can add/subtract multiples of k without changing the result, and those 99...9 are multiples of both 3 and 9. So 123456 is a multiple of 3 (or 9) iff 1 * 1 + 2 * 1 + 3 * 1 + 4 * 1 + 5 * 1 + 6 * 1 = 1 + 2 + 3 + 4 + 5 + 6 is. Apply the same rule as often as you want -- that is, until you only have one digit left, because then it won't get simpler anymore.
- wbl 11mo ago57
- floydian10 11mo ago91 should be prime, ridiculous that it isn't
- sunrunner 11mo agoAgree. Plus now I now need to release a security patch for the hand-rolled crypto library I built.
- deleted 11mo ago[deleted]
- sunrunner 11mo agoI wonder what the underlying human intuition is for 'prime-ness' and why it might break down with larger numbers. Odd numbers in the rightmost position? The 'shape' of the number (phonaesthesia, the bouba/kiki effect)? Maybe they just sort of feel scary?
- IsTom 11mo agoFor n < 100 to be composite you need a factor < sqrt(100) = 10. Rules for 2, 3, 5 are easy to try quickly. That leaves 7, but up to 7*9 you should remember it from multiplication tables. 77 is quite obviously divisible by 11 too, and then it's 7*13 = 91 as the last boss. But I feel that once you realize how special 91 is in that context, you won't forget it again.
- chrisshroba 11mo agoExcept 91