Re:Is this prime?
by cyborgx7 on Tuesday March 08, 2016 @11:39AM
(#11246357)
Same here. What happened to me is, instead of asking myself "Is this a prime number?" I
kept starting to ask myself "Can this number be expressed as a multiplication of two other numbers?" for which the answers are obviously reversed.
[ Parent
| on HN ]
Re:Is this prime?
by davidamarquis on Tuesday March 08, 2016 @12:36PM
(#11246857)
Finding divisors is often hard when your number is large. It turns out the condition that a number n can be expressed as a multiple of two other numbers is equivalent to there being a number z less than n except for 1 and n-1 so that (z^2 mod n) == 1.
This condition is the basis of the Miller-Rabin primality test. Sadly its a bit hard for humans to implement this algorithm for mentally proving primality.