# The Question

A Sophie Germain prime is a prime p such that 2p+1 is prime as well. For example, 11 is a Sophie Germain prime because 23 is prime as well. Write the shortest program to calculate Sophie Germain primes in ascending order

# Rules

• The Sophie Germain primes must be generated by your program, not from an external source.
• Your program must calculate all Sophie Germain primes under 2³²-1
• You must print each distinct Sophie Germain prime your program finds.
• The person with the lowest score wins

# Scoring

• 2 points per byte of your code
• -10 if you can show a prime generated by your program greater than 2³²-1
• Comments are not for extended discussion; this conversation has been moved to chat. – Martin Ender May 11 '15 at 23:41

# CJam

For 17 chars we get full enumeration up to 2^32:

G8#,{_mp*2*)mp},


For 4 chars more, we get a range just large enough to include an SG prime greater than 2^32:

G8#K_*+,{_mp*2*)mp},


since 4294967681 = 2^32 + 385 < 2^32 + 400.

C9#,{_mp*2*)mp},

• This means you can submit it without the bonus for 17 characters or with the bonus for 21 characters – Meow Mix May 11 '15 at 21:02
• @user3502615, or with the bonus for 17 characters. Although it's debatable whether the SG prime I list was actually generated "by my program", since I don't have a powerful enough computer to run it that far. – Peter Taylor May 11 '15 at 21:04
• I, treats I as a signed 32-bit integer, so the maximum value for I is 2 ** 31 - 1. – Dennis May 11 '15 at 21:07
• @Dennis, is that a documented property of the language or an implementation quirk of the Java implementation? – Peter Taylor May 11 '15 at 21:11
• It's not documented, but the behavior is consistent for both the Java and the online interpreter. – Dennis May 11 '15 at 21:13

# Pyth, 19 bytes * 2 - 10 = 28

Note that the online compiler/executor doesn't show output because it's an infinite loop.

K1#~K1I&!tPK!tPhyKK


Explained:

K1                      K=1
#                     While true:
~K1                  K+=1
I                 If
&                logical AND
!tPK            K is prime
!tPhyK      2*K+1 is prime (y is double, h is +1)
K     Print K

• PZ doesn't return a truthy or falsy value. It returns the prime factorization of Z. Testing for prime is !tPZ, which checks if the prime factorization only contains one factor. – Jakube May 11 '15 at 21:39
• Yes. Now it works. !tP mistakes 0 and 1 to be prime though, since their prime factorization only contains 1 factor. Easy fix is to replace all Z by K and assign K2 at the beginning. – Jakube May 11 '15 at 21:45
• Some other golfs: assign K1 instead of K2, and swap the if and the increment. This way you can remove the ). And +1*K2 is the same thing as hyK. – Jakube May 11 '15 at 21:49
• Ah, I had just read about those on the tutorial page. Does it work for you on pyth.herokuapp.com/?code=K2%23I%26!tPK!tPhyKK)~K1&debug=0 – mbomb007 May 11 '15 at 21:51
• The online compiler doesn't show a result, because the program is stuck in an infinite loop. And the website shows only output, after the program finishes. I've tested the code using the offline compiler. It works. – Jakube May 11 '15 at 21:57

# Pyth - 2 * 16 bytes - 10 = 22

Uses the customary method of prime checking in Pyth with the !tP and applies it both to the number and its safe-prime, with a little trick to check both at once. Goes up to 10^10, so I'm going for the bonus.

f!+tPTtPhyTr2^TT


Explanation coming soon.

f          r2^TT     Filter from 2 till 10^10
!                   Logical not to detect empty lists
+                  List concatenation
tP                All but the firs element of the prime factorization
T                The filter element
tP                All but the firs element of the prime factorization
hyT              2n+1

• This takes a machine with about 40 GB of RAM memory. Quite efficient ;-) – Jakube May 11 '15 at 21:26
• I don't think you can claim the - 10 unless you have actually successfully run the code? – orlp May 11 '15 at 23:53
• @orlp no, I asked OP and he said making the range smaller and simulating the whole program would be sufficient: chat.stackexchange.com/transcript/message/21585393#21585393 – Maltysen May 12 '15 at 0:17
#include<stdio.h>
#include<math.h>

int isprime(int);
int main(){
int check,n,secondcheck;
printf("enter how long you want to print\n");
scanf("%d",&n);
for(int i=2;i<n;i++){
check = isprime(i);
if(check==0){
secondcheck = isprime(2*i+1);
if(secondcheck==0){
printf("%d\t",i);
}
else
continue;
}
}
}
int isprime(int num){
int check = num,flag=0;
num = sqrt(num);
for(int i=2;i<=num;i++){
if(check%i==0){
flag=1;
return 1;
}
}
if(flag==0){
return 0;
}
}

• Please consider golfing your program (by removing space ..etc) and see how far you can get. – Mhmd Sep 22 '15 at 11:50

# CJam, 34 (2 * 22 - 10)

C9#{ImpI2*)mp&{Ip}&}fI


Prints all Sophie Germain primes under 12 ** 9, which includes 4294967681 > 2 ** 32.

I estimate that this will take roughly 8 hours on my machine. I'll run it tonight.

# Haskell, 2*54-10 = 98 132

i a=all((>0).rem a)[2..a-1]
p=[n|n<-[2..],i n,i$2*n+1]  i is a prime check. p takes all numbers n where both n and 2*x+1 are prime. p is an infinite list. Edit: better way for checking if 2*n+1 is prime. # Julia, 2*49 - 10 = 88 p=primes(2^33) print(p[map(n->isprime(2n+1),p)])  Prints them in list format, [2,3,5,11,...]. If that format, using the primes function, or waiting until all the computation is done to print isn't acceptable, this prints them one per line as it runs. isprime=f for i=1:2^33;f(i)&&f(2i+1)&&println(i)end  It's a little longer, 52 chars. Both compute all the Sophie Germain primes up to 2^33, so they should get the 10 point discount. # Python 3, 124 123 bytes i=3 q=[2] while 1: p=1 for x in range(2,round(i**.5)+1):p=min(p,i%x) if p: q+=[i];s=(i-1)/2 if s in q:print(s) i+=2  How does it work? i=3 # Start at 3 q=[2] # Create list with first prime (2), to be list of primes. while 1: # Loop forever p=1 # Set p to 1 (true) for x in range(2,round(i**0.5)+1): # Loop from 2 to the number's square root. x is the loop value p=min(p,i%x) # Set p to the min of itself and the modulo of # the number being tested and loop value (x). # If p is 0 at the end, a modulo was 0, so it isn't prime. if p: # Check if p is 0 q+=[i] # Add the current number (we know is prime) to list of primes (q) s=(i-1)/2 # Generate s, the number that you would double and add 1 to make a prime. if s in q:print(s) # If (i-1)/2 is a prime (in the list), then that prime satifies # the condition 2p+1 is prime because i is 2p+1, and i is prime i+=2 # Increment by 2 (no even numbers are prime, except 2)  Try it online here. My computer says it is has generated 0.023283 % of all the Sophie Germain primes below 2^32. When it's finished, I'll post it on pastebin if there are enough lines. You can use it to check you've got them all. • .5 is shorter than 0.5 – mbomb007 May 11 '15 at 21:30 # Perl, 2*57-10 = 104 use ntheory":all";forprimes{say if is_prime(2*$_+1)}2**33

2
3
5
11
...
8589934091
8589934271


42 seconds to 2^32, 1m26s to 2^33. Will run 50% faster if 2*$_+1 is written as 1+$_<<1 but that's one more byte.

The module also installs primes.pl which has lots of filters including one for Sophie-Germain primes. So: primes.pl --so 2**33 (20 bytes)

# Ruby, 61*2 - 10 = 112

require'prime';Prime.each(1.0/0)do|n|p Prime.prime?(n*2+1)end


It would take forever to print out all values up to 2**32

# Edit

Shaved off a few bytes substituting Float::INFINITY for 1.0/0

# PARI/GP, 46 * 2 - 10 = 82

forprime(p=2,2^33,if(isprime(2*p+1),print(p)))
`