Courtesy of Alex Healy Another computation. > > Finding a Sophie Germain prime p = 2*q + 1, where p ~ 2^(300) > and q is a prime. Can you write it out in decimal and how long did it take. > Write out p and q. Hope you can do it within the coming 25 minutes. > > M. q = 324630254359675257495857855638157231343649935469340232504652177847030084435265\ 770988787793 p = 2q + 1 = 649260508719350514991715711276314462687299870938680465009304355694060168870531\ 541977575587 By choosing q's randomly (and no intelligent sieving whatsoever, this took about 1.4 seconds to find on my laptop. >> The fraction of integers not divisible by any prime p < 300 is >> >> (1 - 1/2)(1 - 1/3)(1 - 1/5) . . . (1 - 1/293) = 0.0974585... >> >> (Sanity check: CRT ==> for large n: Pr[p | n] and Pr[q | n] are >independent.) >> >> Just for fun, here are the fractions for other bounds: >> >> 100: 0.1203 >> 200: 0.1039 >> 300: 0.0975 >> 400: 0.0931 >> 500: 0.0896 >> 600: 0.0874 >> 700: 0.0852 >> 800: 0.0836 >> . . . >>