><<Now we can filter out multiples of small primes>>
>I'm assuming that we don't need to divide by factors divisible by 3 or 5,
>etc, because a Mersenne number cannot be divisible by 3 or 5 because they
>don't have the structure 2kp+1 themselves? (Excluding the REALLY low Mersenne
>numbers). Ideally, we'd like to only test factors that are prime
>themselves.... Am I right?
If I understand you, then you are asking if we ever need to test mersenne
numbers for divisibility by 3 or 5. These factors are never considered
because they are not of the form 2*k*p+1, so on that regard you are correct.
However, he is talking about testing potential factors *of mersenne numbers*
for divisibility by such small primes.
If you reread Brian's seive code you will see that here is what he is doing:
he creates an array of 3*5*7*11*13*17=255255 elements. Then he eliminates
every 3rd, 5th, 7th, 11th, 13th, and 17th element. Therefore, he can any
number mod 255255 whose remainder wasn't eliminated in the seiving is not
divisible by 3, 5, 7, 11, 13, or 17. We can also use the value p mod 255255
to allow us to find the value (2*k*p+1) mod 255255
(since a*b mod c is equal to (a mod c)*(b mod c) mod c). So, we can precompute
multiples of p mod 255255, and add them based on the sieve table.
-Lucas Wiman
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
