List Sophie Germain primes

Question

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^{32}-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^{32}-1\$

Answer 1

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

Answer 2

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.

Of course, we could equally extend the range for free as

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

Answer 3

Husk, 16 8 7 * 2 - 10 = 4

-8 12 thanks to @Jo King

fȯṗ→Dİp

Try it online!

A list of all natural numbers that are Sophie Germain primes. I hope it's valid, because it doesn't terminate when you try to show the entire list, but Husk lazily evaluates it, so you can just take the required amount.

fȯṗ→Dİp
f         Filter
     İp   the prime numbers
    D     that, when doubled
   →      and incremented by 1
 ȯṗ       are prime

Another way to do it, also 7 bytes:

fṗm÷2İp

Answer 4

05AB1E, 7 bytes, score = 4

Thanks to @ovs for -1 byte!

∞ʒx>‚pP

(Technically) Prints an infinite list of Sophie Germain primes! (Hence, score is subtracted by 10)

Try it online!

How?

∞ʒ        # For each natural number 'p'...
  x>‚     # Pair p with 2p + 1 (The ‚ is not a comma, it is a weird sort of quotation)
     p    # Are they both prime?
      P   # Then multiply the boolean values! (And implicitly print if the product is 1)

Answer 5

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

Try under 1000 online.

Answer 6

APL (Dyalog Extended), 10 - ⍨ 2 × 27 = 44

f←{⎕←⍵⍴⍨⌽∧\1⍭⍵,1+2×⍵⋄∇⍵+1}1+⊢

Try it online!

Made with some golfing help and general APL help from dzaima.

Explanation

{⎕←⍵⍴⍨⌽∧\1⍭⍵,1+2×⍵⋄∇⍵+1}1+⊢
                        1+⊢ add 1 to the input (initially, 1)
             1+2×⍵          double and increment it
         1⍭⍵,               prepend the primality check(1 or 0)
       ∧\                   and scan with LCM
   ⍵⍴⍨⌽                     reverse & reshape using self
                            (if test is falsy, then this results in ⍬)
 ⎕←                         and display it with newline

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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)

Answer 12

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

Answer 13

PARI/GP, 46 * 2 - 10 = 82

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

Answer 14

Python 3, 2 * 64 bytes - 10 = 118

n=1
while 1:n+=1;all((n-~n)*n%k for k in range(2,n))>0!=print(n)

Try it online!

It turns out a normal prime test is shorter.

---

Python 3, 2 * 67 bytes - 10 = 124

P=k=1
d=[]
while 1:P*=k*k;k+=1;P%k*k//2in d!=print(k//2);d+=P%k*[k]

Try it online!

This uses Wilson's theorem to generate a list of primes. When k is prime and k//2 is prime as well (in d), this prints k//2.

This can be done a little more memory efficient by not collecting a list of primes but rather doing two prime tests at once at the cost of 4 bytes:

P=k=1
m=3;R=4
while 1:P*=k*k;k+=1;R*=m*m*-~m*-~m;m+=2;P%k*R%m>0!=print(k)

Try it online!

Answer 15

Stax, 14 bytes

ü♀σJàx╧☺▼∟╓X≥╣

Run and debug it

Answer 16

Vyxal, 6 bytes, score 2

Þp:d›↔

Try it Online!

     ↔ # Union of...
Þp     # Primes
  :d›  # Primes * 2 + 1

-10 score because it prints an infinite list.

Answer 17

Jelly, 10 bytes => score 10

ȷ10ÆRḤ‘ẒƊƇ

Generates primes up to 10^10 > 2^32.

Try it online! (TIO link is to a shorter version that generates only up to 1000, so it doesn't time out)

Answer 18

Pyt, 11 bytes, score 12

9ᴇřᵽĐ2*⁺ṗ*ž

Try it online!

9ᴇřᵽ    generates the first 1,000,000,000 primes (there are 203,280,221 primes less than 2^32)
Đ2*⁺    calculates 2*p+1 for each prime
ṗ       is each 2*p+1 prime
*       multiply the two lists one element at a time
ž       remove all zeroes from list; implicit print

Answer 19

Thunno, \$ 20 \log_{256}(96) \approx \$ 16.46 bytes, score \$ \approx \$ 22.92

[xNx2*1+N&?xZK((x1+X

Explanation

[                     # while True:
 xN                   #  x is prime?
   x2*1+N             #  x*2+1 is prime?
         &?           #  if both are true:
           xZK        #   print x
              ((      #  endif
                x1+X  #  x=x+1

Screenshot