News for hackers. Stuff that matters.
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.
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.