Primality checking is simple to do in parallel. Imagine that you want to check number n = 2**n - 1:

1. You generate sequence of primes from 2 to 2**(n/2) - 1 as if number is not prime, then it will have divisor there.
2. Each machine that want to participate in testing now will request divisor d to test against and will check if n % d == 0
3. If result is true, then you send result to the central server that this is not prime, if you get false then you send that it is potential prime.
4. If result was false then you go to the step 2 as long as all potential divisors aren’t tested.