3 ms·
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.
by Nevermark 11mo ago
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.
- WCSTombs 11mo agoThe 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.
- great_wubwub 11mo ago/r/whoosh
- eps 11mo agoNah, the joke just was fairly flat and low-effort.
- Nevermark 11mo agoAh, 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.
- mysterydip 11mo agoPerfect example of how "if the code is compact, it's fast" can be deceiving :)
- Nevermark 11mo agoSearch is all you need! If you have the time. Or if we can expand quantum superposition algorithms from 2^N states, for quantum circuits with N control qubits, to 2^(T*N) superpositions over T time steps, via some kind of superposition tree recursion. The number of superpositions increasing exponentially for T steps (and then reducing for another T steps) on a single recursive physical circuit. That is not supported by the physical laws we have, but it is an interesting idea.
- xpe 11mo agoThe 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).
- gsliepen 11mo agoYou are assuming division itself is an O(1) operation. However, it also scales with the size of the number. So more correct would be to say that this naive method is O(sqrt(N) log(N) log(log(N))).
- xpe 11mo agoI was both hoping and fearing that someone would correct my simplification. (That is more nested logs than I would’ve guessed however.)
- deleted 11mo ago[deleted]
- tmtvl 11mo agoEven better: you only have to check primes smaller than or equal to the square root.