Thread: Calculation 300 digit Sophie Germain prime number

I have been set a challenge to produce a 300 digit Sophie Germain prime number using computer code.

Maths at this level is not something that I use a great deal and certain not with these size of numbers. So I apologise if this is all a bit "basic".

Working on the basis of A prime number p is a [COLOR=rgb(0.000000%, 69.400000%, 31.400000%)]Sophie Germain Prime, [/COLOR]when also 2p + 1 is a prime.

But, I need to generate this result in the most efficient method possible and would like any assistance or advice on how to produce such a number without making my starting point of 3 and working up to this size of number. Is there a more efficient method to achieve this?

Any assistance would be greatly appreciated.

No! There's no reason to start with 3! Why not start with ? There's no magic formula that I know of to produce these things, but in the 300 digit range, about .14% of numbers are prime, so the starting odds of p and 2p+1 being prime are one in about 475000. Sure, that's a half a million primality tests, but it certainly beats starting at 3.

If it was me, I would start with a table of a million or so random 300 digit numbers, along with their "partners" giving you random pairs (p,2p+1) in the range you're looking for. Then sieve out the evens, multiples of 3, then 5, 7, 11, etc, until you get to about . Whatever you have left over, use a high-powered primality test like Lucas-Lehmer to eliminate your pairs. You might be able to get away with only a few thousand tests after sieving.