News for hackers. Stuff that matters.
Re:2^74207281-1 is Prime by ajuc on Tuesday January 19, 2016 @01:40PM (#10932824)
You only need to divide by prime numbers up to ceil(sqrt(your_number)).

They don't know all prime numbers up to this number, but they can easily exclude many numbers (for example even).

Re:2^74207281-1 is Prime by kale on Tuesday January 19, 2016 @02:24PM (#10933209)
That would still take an eternity.

They use special form primes (the big primes are all n+1 or n-1 forms, with n being easy to factor).

If a Mersenne Number is prime, then the exponent must also be prime (74,207,281 is also prime). That cuts down on a lot of processing time.

Also, all factors of a Mersenne Number, if it's composite, are of the form 2nk + 1, where the Mersenne number is written 2^n - 1. That also helps factor it. I generated a huge list of prime number indices and did some tests on them a couple of years ago. 25% of the Mersenne numbers have 2*n + 1 as a factor. That's even less computation time to find a large prime.

Re:2^74207281-1 is Prime by skj on Tuesday January 19, 2016 @02:56PM (#10933467)
Or any composite number. If it's divisible by a composite number, it will also be divisible by the smaller primes.
Re:2^74207281-1 is Prime by spdionis on Tuesday January 19, 2016 @03:48PM (#10933880)
This are the simplest insights for optimizing primality test. A nice exercise to implement if you like algorithms. More info: https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes