Safe and Sophie Germain primes
A prime number p is Sophie Germain prime if 2p + 1 is also prime.
- See the same at Safe_primes_and_unsafe_primes
The number 2p + 1 associated with a Sophie Germain prime is called a safe prime.
- Task
Generate the first 50 Sophie Germain prime numbers.
ALGOL 68
<lang algol68>BEGIN # find some Sophie Germain primes: primes p such that 2p + 1 is prime #
PR read "primes.incl.a68" PR []BOOL prime = PRIMESIEVE 10 000; # hopefully, enough primes # INT sg count := 0; FOR p WHILE sg count < 50 DO # find the first 50 Sophie Germain primes # IF prime[ p ] THEN IF prime[ p + p + 1 ] THEN print( ( " ", whole( p, -6 ) ) ); IF ( sg count +:= 1 ) MOD 12 = 0 THEN print( ( newline ) ) FI FI FI OD
END</lang>
- Output:
2 3 5 11 23 29 41 53 83 89 113 131 173 179 191 233 239 251 281 293 359 419 431 443 491 509 593 641 653 659 683 719 743 761 809 911 953 1013 1019 1031 1049 1103 1223 1229 1289 1409 1439 1451 1481 1499
jq
Works with gojq, the Go implementation of jq
See e.g. #Find_adjacent_primes_which_differ_by_a_square_integer#jq for suitable implementions of `is_prime/0` and `primes/0` as used here. <lang jq>limit(50; primes | select(2*. + 1|is_prime))</lang>
- Output:
2 3 5 ... 1451 1481 1499
Julia
<lang julia>using Primes
for (i, p) in enumerate(filter(x -> isprime(2x + 1), primes(1500)))
print(lpad(p, 5), i % 10 == 0 ? "\n" : "")
end
</lang>
- Output:
2 3 5 11 23 29 41 53 83 89 113 131 173 179 191 233 239 251 281 293 359 419 431 443 491 509 593 641 653 659 683 719 743 761 809 911 953 1013 1019 1031 1049 1103 1223 1229 1289 1409 1439 1451 1481 1499
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Safe_and_Sophie_Germain_primes use warnings; use ntheory qw( forprimes is_prime);
my @want; forprimes { is_prime(2 * $_ + 1) and (50 == push @want, $_)
and print("@want\n" =~ s/.{65}\K /\n/gr) + exit } 2, 1e9;</lang>
- Output:
2 3 5 11 23 29 41 53 83 89 113 131 173 179 191 233 239 251 281 293 359 419 431 443 491 509 593 641 653 659 683 719 743 761 809 911 953 1013 1019 1031 1049 1103 1223 1229 1289 1409 1439 1451 1481 1499
Phix
with javascript_semantics function sophie_germain(integer p) return is_prime(2*p+1) end function sequence res = {} integer n = 1 while length(res)<50 do integer p = get_prime(n) if sophie_germain(p) then res &= p end if n += 1 end while printf(1,"First 50: %s\n",{join(shorten(apply(res,sprint),"",5))})
- Output:
First 50: 2 3 5 11 23 ... 1409 1439 1451 1481 1499
Raku
<lang perl6>put join "\n", (^∞ .grep: { .is-prime && ($_*2+1).is-prime } )[^50].batch(10)».fmt: "%4d";</lang>
- Output:
2 3 5 11 23 29 41 53 83 89 113 131 173 179 191 233 239 251 281 293 359 419 431 443 491 509 593 641 653 659 683 719 743 761 809 911 953 1013 1019 1031 1049 1103 1223 1229 1289 1409 1439 1451 1481 1499
Wren
<lang ecmascript>import "./math" for Int import "./seq" for Lst import "./fmt" for Fmt
var sgp = [] var p = 2 var count = 0 while (count < 50) {
if (Int.isPrime(p) && Int.isPrime(2*p+1)) { sgp.add(p) count = count + 1 } p = (p != 2) ? p + 2 : 3
} System.print("The first 50 Sophie Germain primes are:") for (chunk in Lst.chunks(sgp, 10)) Fmt.print("$,5d", chunk)</lang>
- Output:
The first 50 Sophie Germain primes are: 2 3 5 11 23 29 41 53 83 89 113 131 173 179 191 233 239 251 281 293 359 419 431 443 491 509 593 641 653 659 683 719 743 761 809 911 953 1,013 1,019 1,031 1,049 1,103 1,223 1,229 1,289 1,409 1,439 1,451 1,481 1,499
XPL0
<lang XPL0>func IsPrime(N); \Return 'true' if N is a prime number int N, I; [for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true; ];
int N, Count; [N:= 2; Count:= 0; repeat if IsPrime(N) & IsPrime(2*N+1) then
[IntOut(0, N); ChOut(0, 9\tab\); Count:= Count+1; if rem(Count/10) = 0 then CrLf(0); ]; N:= N+1;
until Count >= 50; ]</lang>
- Output:
2 3 5 11 23 29 41 53 83 89 113 131 173 179 191 233 239 251 281 293 359 419 431 443 491 509 593 641 653 659 683 719 743 761 809 911 953 1013 1019 1031 1049 1103 1223 1229 1289 1409 1439 1451 1481 1499