13
\$\begingroup\$

This question already has an answer here:

A Sophie Germain Prime is a prime number P such that 2P+1 is prime as well. Given a prime number as input, your task is to determine whether it is a Sophie Germain Prime.

Standard Input/Output rules and Default Loopholes apply. This is a , so standard rules for this tag apply (returning two distinct and consistent values for each case, e.g: True/False).


Test Cases

Truthy (Sophie Germain primes)

These are the first few of them (OEIS A005384):

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113

Falsy

7, 13, 17, 31, 37, 43, 47

Please note that answers with explanations are encouraged!

It's , hence the shortest code in bytes in every language wins!

\$\endgroup\$

marked as duplicate by Wheat Wizard, xnor code-golf Jul 9 '17 at 17:55

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Can I flip the True/False (i.e. output "False" if the prime is a SG prime, "True" otherwise)? \$\endgroup\$ – Qwerp-Derp Jul 9 '17 at 12:18
  • 7
    \$\begingroup\$ Personally, I think ir would have been best to not gusrantee primality of the input. \$\endgroup\$ – Okx Jul 9 '17 at 13:47
  • 1
    \$\begingroup\$ Does "returning two distinct values for each case" imply the values must be consistent rather than the tag text "either truthy or falsy" or may we return inconsistent, but if-testable, values? \$\endgroup\$ – Jonathan Allan Jul 9 '17 at 14:15
  • 6
    \$\begingroup\$ You should have a set of values for truthy and their complement for falsy, if you choose to have them inconsistent. Can I define SG primes as truthy values? :P \$\endgroup\$ – Dennis Jul 9 '17 at 14:51
  • 9
    \$\begingroup\$ I'm not going to vote to close because I have a dupe hammer, but this seems like it's a dupe of Is it a prime?, since the only difference is that the input isn't the number you're testing. Adding the offset (2n + 1) is a pretty trivial modification. \$\endgroup\$ – DJMcMayhem Jul 9 '17 at 16:33

28 Answers 28

7
\$\begingroup\$

x86-64 Machine Code, 24 bytes

01 FF FF C7 6A 01 59 89 F8 FF C1 99 F7 F9 85 D2 75 F5 39 F9 0F 94 C0 C3

The above code defines a function that takes a single parameter (the input value, known to be a prime) in EDI (following the System V AMD64 calling convention used on Gnu/Unix), and returns a Boolean result in AL (1 if the input is a Sophie Germain prime, 0 otherwise).

The implementation is very similar to the solution to this challenge, since all we really have to do is determine whether a number is prime using as little code as possible, which means an inefficient iterative loop.

Basically, we take the input and immediately transform it into 2 × input + 1. Then, starting with a counter set to 2, we loop through and check to see if the counter is a factor. The counter is incremented each time through the loop. As soon as a factor is found, the loop ends and that factor is compared against 2 × input + 1. If the factor is equal to the test value, then that means we didn't find any smaller factors, and therefore the number must be prime. And since we have thus confirmed that 2 × input + 1 is prime, this means that input must be a Sophie Germain prime.

Ungolfed assembly language mnemonics:

IsSophieGermainPrime:
   add   edi, edi            ; input *= 2
   inc   edi                 ; input += 1
   push  1
   pop   rcx                 ; counter = 1

.CheckDivisibility:
   inc   ecx                 ; increment counter
   mov   eax, edi            ; EAX = input (needs to be in EAX for IDIV; will be clobbered)
   cdq                       ; sign-extend EAX into EDX:EAX
   idiv  ecx                 ; EDX:EAX / counter
   test  edx, edx            ; check the remainder to see if divided evenly
   jnz   .CheckDivisibility  ; keep looping if not divisible by this one

   cmp   ecx, edi            ; compare counter to input
   sete  al                  ; set true if first found factor is itself;
   ret                       ;          otherwise, set false
\$\endgroup\$
6
\$\begingroup\$

Python,  46 43 41  40 bytes

-1 byte using code suggested elsewhere by Erik the Outgolfer (2*n+1 may be calculated as n-~n - that is, 2*n+1=n-(-1-n))

f=lambda n,p=3:p>n or(n-~n)%p*f(n,p+2)>0

A recursive function.

Returns True if the prime number input, n, is a Sophie Germain prime and False if not.

Try it online!

Works by multiplying the remainders of the division of the candidate number n-~n (which is equal to 2*n+1) after dividing by p, while p is less than n, starting at p=3 and incrementing by 2 at each iteration. This is sufficient since n is greater that the square root of 2*n+1 (n-~n) for n greater than 2. Also, since 2 is a Sophie Germain prime we can start testing with p=3 and add 2 at each iteration rather than 1. If the original n was greater than 2 the product of the resulting remainders is returned, so if the candidate has any factors the resulting 0 forces the result to be 0 too. The final >0 forces all the positive products to return True and the 0s to return False (to fulfil the "distinct and consistent" requirement).

Also beats:

...the 41 byte Python 3 (with sympy):

import sympy
lambda n:sympy.isprime(n-~n)

...and the 42 byte Python 2 full program Try It:

n=2*input()+1
p=3
while n%p:p+=2
print p<n
\$\endgroup\$
  • \$\begingroup\$ You do not need the brackets \$\endgroup\$ – Mr. Xcoder Jul 9 '17 at 12:32
  • \$\begingroup\$ 44 bytes, forgot to remove the space \$\endgroup\$ – Mr. Xcoder Jul 9 '17 at 12:33
  • \$\begingroup\$ @Mr.Xcoder was busy editing in for 43...I noticed :) \$\endgroup\$ – Jonathan Allan Jul 9 '17 at 12:34
  • 1
    \$\begingroup\$ What is it with these weird looking recursive functions and out-golfing me... \$\endgroup\$ – totallyhuman Jul 9 '17 at 13:05
  • \$\begingroup\$ @EriktheOutgolfer I wrote about that in the answer - the OP requests "two distinct values for each case", I had meant to ask, and have now. \$\endgroup\$ – Jonathan Allan Jul 9 '17 at 14:16
6
\$\begingroup\$

Python 2, 39 bytes

f=lambda n,k=3:n%k^k/2>0<f(n,k+2)or k>n

Try it online!

Alternate versions

f=lambda n,k=3:n%k^1>0<f(n-1,k+2)or k>n
f=lambda n,k=3:~-n%k>0<f(n-1,k+2)or k>n
f=lambda n,k=3:n%k!=1==f(n-1,k+2)or k>n
\$\endgroup\$
  • 3
    \$\begingroup\$ I usually don't ask for one on Python answers... But could we have an explanation as to what is going on? \$\endgroup\$ – totallyhuman Jul 9 '17 at 18:53
  • \$\begingroup\$ I've recreated the top solution in a more verbose way, altering some of the code but leaving the same logic. Though I'm still not quite sure why it works. \$\endgroup\$ – musicman523 Jul 10 '17 at 6:19
  • \$\begingroup\$ @totallyhuman If (2*n+1)%k gives 0, n%k gives either 0 or (k-1)/2. Since n is prime, n%k cannot give 0, so it suffices to check for the latter case. I'll add a more detailed explanation tomorrow. \$\endgroup\$ – Dennis Jul 10 '17 at 7:25
4
\$\begingroup\$

MATL, 4 bytes

EQZp

Prints 1 for a Sophie Germain prime and 0 otherwise.

Try it at MATL Online

Explanation

        % Implicitly grab input as a number
E       % Multiply by 2 
Q       % Add one
Zp      % Check if this is a prime number
        % Implicitly display the result
\$\endgroup\$
4
\$\begingroup\$

Mathematica , 13 bytes

PrimeQ[2#+1]&
\$\endgroup\$
  • \$\begingroup\$ TIO link? (mathics) \$\endgroup\$ – Leaky Nun Jul 9 '17 at 12:17
4
\$\begingroup\$

CJam, 7 bytes

{2*)mp}

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Pyth, 4 bytes

Almost an anagram for Pyth.

P_hy

Try it online!

Other semi-anagrams: Pt_y, P_tyh.

How?

   y   # Double
  h    # Increment
 _     # Negate
P      # Prime?

P for positive argument factorizes; to test primality one should provide the negation of the number tested.

\$\endgroup\$
  • \$\begingroup\$ Why do you need to negate? \$\endgroup\$ – totallyhuman Jul 9 '17 at 12:21
  • 1
    \$\begingroup\$ @totallyhuman P with negative argument check if -argument is prime, P with positive argument returns list of prime factors \$\endgroup\$ – Uriel Jul 9 '17 at 12:23
  • \$\begingroup\$ It'd be great if you could find a way to make this an anagram of Pyth... \$\endgroup\$ – Beta Decay Jul 9 '17 at 12:47
  • 1
    \$\begingroup\$ @daniero You're assumed prime input. \$\endgroup\$ – Erik the Outgolfer Jul 9 '17 at 12:53
  • \$\begingroup\$ @BetaDecay I can do P_tyh (inc, double, dec) \$\endgroup\$ – Uriel Jul 9 '17 at 12:58
3
\$\begingroup\$

05AB1E, 3 bytes

x>p

Prints 1 if the prime number input is a Sophie Germain prime, and 0 if it is not (prints 1 if double the input plus one is prime).

Try it online!

How?

x>p - implicit input: number n
x   - pop n then push n, 2*n
 >  - pop 2*n then push 2*n+1
  p - pop 2*n+1 then push is prime? (2*n+1) {True:1; False:0}
    - implicit print of top of stack
\$\endgroup\$
3
\$\begingroup\$

Python 2, 47 43 42 bytes

-4 bytes thanks to Leaky Nun. -1 byte thanks to Erik the Outgolfer.

lambda n:all((n-~n)%i for i in range(2,n))

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Do you need to check up to 2*n+1? \$\endgroup\$ – Leaky Nun Jul 9 '17 at 12:06
  • \$\begingroup\$ (2*n+1) can be (n-~n). \$\endgroup\$ – Erik the Outgolfer Jul 9 '17 at 13:48
  • \$\begingroup\$ @EriktheOutgolfer Oh, nice, thanks! \$\endgroup\$ – totallyhuman Jul 9 '17 at 13:49
  • \$\begingroup\$ Basically (2*n+1) can also be (n+n+1) which can be (n+(n+1)), which in turn is the same as (n+-~n) or (n-~n). \$\endgroup\$ – Erik the Outgolfer Jul 9 '17 at 13:51
3
\$\begingroup\$

Brachylog, 5 bytes

×₂+₁ṗ

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 4 bytes

Ḥ‘ÆP

A monadic link returning 1 if the prime number input is a Sophie Germain prime, and 0 if it is not (yields 1 if double the input plus one is prime, 0 otherwise).

Try it online!

How?

Ḥ‘ÆP - Link: number n
Ḥ    - double n
 ‘   - increment
  ÆP - is prime?
\$\endgroup\$
2
\$\begingroup\$

C, 43 bytes

i;f(x){for(x=x*2+1,i=1;x%++i;);return x>i;}

Returns 0 if x is a Sophie Germain prime, 1 otherwise.

Try it online!

C (gcc), 38 bytes

i;f(x){for(x=x*2+1,i=1;x%++i;);x=x>i;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Shave off 2 bytes by using i=1; at the start. \$\endgroup\$ – G. Sliepen Jul 9 '17 at 13:48
  • 2
    \$\begingroup\$ @G.Sliepen Thanks, but then the function would not be reusable, and therefore not a valid submission. \$\endgroup\$ – Steadybox Jul 9 '17 at 14:29
2
\$\begingroup\$

PHP, 39 bytes

prints 1 for true and nothing for false

for($d=$n=$argn*2+1;$n%--$d;);echo$d<2;

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Neim, 3 bytes

ᚫ>𝐌

Try it online!

-1 thanks to Okx.

\$\endgroup\$
  • \$\begingroup\$ Neim has a 1-byte 'check for primality' token. \$\endgroup\$ – Okx Jul 9 '17 at 13:54
  • \$\begingroup\$ @Okx Oh I searched for it. \$\endgroup\$ – Erik the Outgolfer Jul 9 '17 at 13:58
2
\$\begingroup\$

Julia 0.6, 20 bytes

x->∉(0,(x-~x)%3:x)
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Jul 9 '17 at 17:33
1
\$\begingroup\$

Python 2, 55 bytes:

lambda n:len(filter(lambda p:(2*n+1)%p,range(2,n)))>n-3

Python 2, 48 bytes, different logic:

lambda n:all(map(lambda p:(2*n+1)%p,range(2,n)))
\$\endgroup\$
  • \$\begingroup\$ (2*n+1) can be replaced by (n-~n) in both versions. \$\endgroup\$ – Erik the Outgolfer Jul 9 '17 at 13:59
  • \$\begingroup\$ Your first version can simply be lambda n:len(filter((n~-n).__mod__,range(2,n)))>n-3. Second version is essentially the same as totallyhuman's. \$\endgroup\$ – Erik the Outgolfer Jul 9 '17 at 14:01
1
\$\begingroup\$

Clojure, 60 bytes

#((fn[n](some(fn[a](=(mod n a)0))(range 2 n)))(+(* 2 %)1))

Try it online!

This is an anonymous function - to use the function, do this:

(#(...) {number}) ; This will output a value

Returns False if prime is a Sophie Germain prime, True otherwise.

\$\endgroup\$
1
\$\begingroup\$

Japt, 5 bytes

*2Ä j

Test it online! Probably won't get shorter than this...

An alternative solution which might be shorter in other languages:

¤Ä n2 j

Test it online! ¤ converts the input to binary, Ä appends a 1, and n2 converts back from base 2 (Japt doesn't have a built-in for converting from binary).

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 17 bytes

p->isprime(2*p+1)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

QBIC, 7 bytes

?µ:*2+1

Explanation

?        PRINT
 µ       the result of the prime-test (-1 for true. 0 for false)
  :*2+1  with the input times 2 plus 1 as argument
\$\endgroup\$
1
\$\begingroup\$

braingasm, 8 5 bytes

;*+q:

Works like this:

;          Input a number
 *+        Double and increase it
   q:      Print 1 or 0 depending on wether the current number is prime

edit: don't need prime check on input

\$\endgroup\$
  • 2
    \$\begingroup\$ you don't have to test input for primality \$\endgroup\$ – Uriel Jul 9 '17 at 12:53
  • \$\begingroup\$ @Uriel Got it :) \$\endgroup\$ – daniero Jul 9 '17 at 12:55
1
\$\begingroup\$

MATLAB / Octave, 18 bytes

@(x)isprime(2*x+1)

Anonymous function.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Ruby 2.3.1, 44 bytes

lambda{|p|(2...2*p+1).all?{|r|(2*p+1)%r!=0}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

C (gcc), 46 bytes

f(x,i){for(i=2;i<x;)(x-~x)%i++?:(x=i=0);x=!x;}

Try it online!

Returns 0 if SG prime, 1 otherwise.

\$\endgroup\$
  • \$\begingroup\$ What does GCC do with the empty "true" portion of the conditional operator? How does that get interpreted? \$\endgroup\$ – Cody Gray Jul 9 '17 at 15:46
  • 2
    \$\begingroup\$ @CodyGray If the "true" part is empty, the value of the condition is returned instead of it. \$\endgroup\$ – Steadybox Jul 9 '17 at 15:49
  • \$\begingroup\$ @CodyGray Well, it's only returned to nowhere so don't worry. \$\endgroup\$ – Erik the Outgolfer Jul 9 '17 at 16:00
  • \$\begingroup\$ Yes, I realize this is completely invalid and meaningless code that only just barely "works" if the stars are aligned just-so. I've been told that doesn't bother anyone on Code Golf, so I'm just trying my best to ignore it. I was intrigued, though, by the GCC extension with an empty "true" portion of a conditional operator, because I'd never seen that before and it wasn't immediately obvious to me how it worked. @Steadybox answered that with a reference, so much thanks! \$\endgroup\$ – Cody Gray Jul 10 '17 at 7:37
1
\$\begingroup\$

Julia 0.4, 17 16 bytes

1 byte saved thanks to @Tanj

x->isprime(x-~x)

isprime was deprecated in Julia 0.5.

\$\endgroup\$
  • \$\begingroup\$ Identical to the PariGP submission... \$\endgroup\$ – Mr. Xcoder Jul 9 '17 at 12:57
  • \$\begingroup\$ @Mr.Xcoder polyglot then? \$\endgroup\$ – Uriel Jul 9 '17 at 13:02
  • \$\begingroup\$ you can slightly reduce by computing 2*x+1 with x-~x ? \$\endgroup\$ – Tanj Jul 9 '17 at 16:02
  • \$\begingroup\$ 2x+1 is a bit more readable. \$\endgroup\$ – Dennis Jul 9 '17 at 16:44
1
\$\begingroup\$

Excel VBA, 59 Bytes

Anonymous VBE immediate window function that takes input from cell [A1] to and outputs to the vbe immediate window

Must be run in a clean module or the value of j must be reset to 0 before use

n=[2*A1-1]:For i=2To n-1:j=IIf(n/i=Int(n/i),i,j):Next:?j<>0
\$\endgroup\$
0
\$\begingroup\$

,,,, 5 bytes

2×1+p

Unlike other golflangs, ,,, doesn't have builtins for incrementing and doubling because I thought I'd rather use those bytes for other things. :P

Explanation

Take input 23 for example.

2×1+p

       implicit input                      [23]
2      push 2                              [23, 2]
 ×     pop 23 and 2 and push 23 * 2        [46]
  1    push 1                              [46, 1]
   +   pop 46 and 1 and push 46 + 1        [47]
    p  pop 47 and push whether it is prime [1]
       implicit output                     []
\$\endgroup\$
0
\$\begingroup\$

cQuents, 9 bytes

#|2A+1?pz

Had to fix an interpreter bug to get this working, so no TIO link.

Explanation

#|2A+1      The last item in the input, which will become n, equals the first item 
            in the input times two, plus one.
      ?     Mode: query. Returns true if n is in the sequence, and false otherwise.
       pz   Sequence: each item is the next prime after the previous item.
\$\endgroup\$
  • \$\begingroup\$ Note current version uses Z instead of z \$\endgroup\$ – Stephen Feb 1 at 4:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.