Rosetta Code

Safe and Sophie Germain primes: Difference between revisions

Page Discussion

Safe and Sophie Germain primes (view source)

Revision as of 10:06, 4 February 2024

14,893 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(30 intermediate revisions by 19 users not shown)
Line 2:
[[Category:Mathematics]]
 
A prime number ''p'' is [[wp:Safe_and_Sophie_Germain_primes|a Sophie Germain prime]] if 2''p''&nbsp;+&nbsp;1 is also prime.<br>
;<b>See the same at [[Safe_primes_and_unsafe_primes]]</b><br>
The number 2''p''&nbsp;+&nbsp;1 associated with a Sophie Germain prime is called a '''safe prime'''.
;Task
Generate the first &nbsp; '''50''' &nbsp; Sophie Germain prime numbers.
 
 
; See also
 
;* [[wp:Safe_and_Sophie_Germain_primes|Wikipedia: Sophie Germain primes]]
;* [[oeis:A005384|OEIS:A005384 - Sophie Germain primes]]
;* [[Safe_primes_and_unsafe_primes|Related Task: Safe_primes_and_unsafe_primes]]
 
 
=={{header|11l}}==
<syntaxhighlight lang="11l">F is_prime(a)
I a == 2
R 1B
I a < 2 | a % 2 == 0
R 0B
L(i) (3 .. Int(sqrt(a))).step(2)
I a % i == 0
R 0B
R 1B
 
V cnt = 0
L(n) 1..
I is_prime(n) & is_prime(2 * n + 1)
print(n, end' ‘ ’)
I ++cnt == 50
L.break
print()</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-primes}}
<langsyntaxhighlight 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 #
Line 23 ⟶ 54:
FI
OD
END</langsyntaxhighlight>
{{out}}
<pre>
Line 32 ⟶ 63:
1481 1499
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="rebol">sophieG?: function [p][
and? [prime? p][prime? 1 + 2*p]
]
 
sophieGermaines: new [2]
i: 3
while [50 > size sophieGermaines][
if sophieG? i ->
'sophieGermaines ++ i
i: i + 2
]
 
loop split.every:10 sophieGermaines 'a ->
print map a => [pad to :string & 4]</syntaxhighlight>
 
{{out}}
 
<pre> 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</pre>
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SAFE_AND_SOPHIE_GERMAIN_PRIMES.AWK
BEGIN {
limit = 50
printf("The first %d Sophie Germain primes:\n",limit)
while (count < limit) {
if (is_prime(++i)) {
if (is_prime(i+i+1)) {
printf("%5d%1s",i,++count%10?"":"\n")
}
}
}
exit(0)
}
function is_prime(n, d) {
d = 5
if (n < 2) { return(0) }
if (n % 2 == 0) { return(n == 2) }
if (n % 3 == 0) { return(n == 3) }
while (d*d <= n) {
if (n % d == 0) { return(0) }
d += 2
if (n % d == 0) { return(0) }
d += 4
}
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
The first 50 Sophie Germain primes:
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
</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
 
 
 
procedure SophieGermainPrimes(Memo: TMemo);
var I,Cnt: integer;
var S: string;
begin
Cnt:=0;
S:='';
for I:=0 to high(integer) do
if IsPrime(I) then
if IsPrime(2 * I + 1) then
begin
Inc(Cnt);
S:=S+Format('%5D',[I]);
if Cnt>=50 then break;
If (Cnt mod 5)=0 then S:=S+CRLF;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count = '+IntToStr(Cnt));
end;
 
</syntaxhighlight>
{{out}}
<pre>
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
Count = 50
Elapsed Time: 2.520 ms.
 
</pre>
 
 
=={{header|Factor}}==
{{works with|Factor|0.99 2022-04-03}}
<syntaxhighlight lang="factor">USING: lists lists.lazy math math.primes math.primes.lists prettyprint ;
 
50 lprimes [ 2 * 1 + prime? ] lfilter ltake [ . ] leach</syntaxhighlight>
{{out}}
<pre>
2
3
5
...
1451
1481
1499
</pre>
 
=={{header|Fermat}}==
<syntaxhighlight lang="fermat">c:=1;
n:=3;
!!2;
while c<50 do
if Isprime(n) and Isprime(2*n+1) then
c:+;
!!n;
fi;
n:+2;
od;</syntaxhighlight>
 
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
<syntaxhighlight lang="freebasic">function isprime(n as integer) as boolean
if n < 2 then return false
if n < 4 then return true
if n mod 2 = 0 then return false
dim as uinteger i = 1
while i*i<=n
i+=2
if n mod i = 0 then return false
wend
return true
end function
 
function is_sg( n as integer ) as boolean
if not isprime(n) then return false
return isprime(2*n+1)
end function
 
dim as uinteger c = 1, i = 1
print "2 ";
while c<50
i+=2
if is_sg(i) then
print i;" ";
c+=1
if c mod 10 = 0 then print
end if
wend</syntaxhighlight>
{{out}}<pre>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</pre>
 
==={{header|GW-BASIC}}===
<syntaxhighlight lang="gwbasic">10 PRINT "2 ";
20 C = 1
30 N = 3
40 WHILE C < 51
50 P = N
60 GOSUB 170
70 IF Z = 0 THEN GOTO 140
80 P = 2 * N + 1
90 GOSUB 170
100 IF Z = 0 THEN GOTO 140
110 C = C + 1
120 PRINT N;" ";
130 IF C MOD 10 = 0 THEN PRINT
140 N = N + 2
150 WEND
160 END
170 Z = 0
180 IF P < 2 THEN RETURN
190 Z = 1
200 IF P < 4 THEN RETURN
210 Z = 0
220 IF P MOD 2 = 0 THEN RETURN
230 I = 3
240 WHILE I*I<P
250 IF P MOD I = 0 THEN RETURN
260 I = I + 1
270 WEND
280 Z = 1
290 RETURN</syntaxhighlight>
 
==={{header|BASIC256}}===
<syntaxhighlight lang="freebasic">function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function
 
function isSG(n)
if not isPrime(n) then return False
return isPrime(2*n+1)
end function
 
c = 1
i = 1
print "2 ";
while c < 50
i += 2
if isSG(i) then
print i; chr(9);
c += 1
if c mod 10 = 0 then print
end if
end while
end</syntaxhighlight>
 
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">Procedure isPrime(v.i)
If v <= 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
ElseIf v % 2 = 0 : ProcedureReturn #False
ElseIf v < 9 : ProcedureReturn #True
ElseIf v % 3 = 0 : ProcedureReturn #False
Else
Protected r = Round(Sqr(v), #PB_Round_Down)
Protected f = 5
While f <= r
If v % f = 0 Or v % (f + 2) = 0 :
ProcedureReturn #False
EndIf
f + 6
Wend
EndIf
ProcedureReturn #True
EndProcedure
 
Procedure isSG(n.i)
If Not isPrime(n) : ProcedureReturn #False : EndIf
ProcedureReturn isPrime(2*n+1)
EndProcedure
 
OpenConsole()
c.i = 1
i.i = 1
Print("2 ")
While c < 50
i + 2
If isSG(i):
Print(Str(i) + #TAB$)
c + 1
If c % 10 = 0 : PrintN("") : EndIf
EndIf
Wend
Input()
CloseConsole()</syntaxhighlight>
 
==={{header|Yabasic}}===
<syntaxhighlight lang="freebasic">sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
 
sub isSG(n)
if not isPrime(n) then return False : fi
return isPrime(2*n+1)
end sub
 
c = 1
i = 1
print "2 ";
while c < 50
i = i + 2
if isSG(i) then
print i, " ";
c = c + 1
if mod(c, 10) = 0 then print : fi
endif
wend
end</syntaxhighlight>
 
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<syntaxhighlight lang="go">package main
 
import (
"fmt"
"rcu"
)
 
func main() {
var sgp []int
p := 2
count := 0
for count < 50 {
if rcu.IsPrime(p) && rcu.IsPrime(2*p+1) {
sgp = append(sgp, p)
count++
}
if p != 2 {
p = p + 2
} else {
p = 3
}
}
fmt.Println("The first 50 Sophie Germain primes are:")
for i := 0; i < len(sgp); i++ {
fmt.Printf("%5s ", rcu.Commatize(sgp[i]))
if (i+1)%10 == 0 {
fmt.Println()
}
}
}</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|J}}==
 
<syntaxhighlight lang=J> 5 10$(#~ 1 2&p. e. ])p:i.1e5
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</syntaxhighlight>
 
=={{header|jq}}==
Line 37 ⟶ 445:
'''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.
<langsyntaxhighlight lang="jq">limit(50; primes | select(2*. + 1|is_prime))</langsyntaxhighlight>
{{out}}
<pre>
Line 52 ⟶ 460:
 
=={{header|Julia}}==
<langsyntaxhighlight 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
</langsyntaxhighlight>{{out}}
<pre>
2 3 5 11 23 29 41 53 83 89
Line 65 ⟶ 473:
1049 1103 1223 1229 1289 1409 1439 1451 1481 1499
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">nextSafe[n_] :=
NestWhile[NextPrime, n + 1, ! (PrimeQ[2 # + 1] && PrimeQ[#]) &]
Labeled[Grid[Partition[NestList[nextSafe, 2, 49], 10],
Alignment -> {Right,
Baseline}], "First 50 Sophie Germain primes:", Top]</syntaxhighlight>
 
{{out}}<pre>
First 50 Sophie Germain primes:
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
</pre>
 
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
/* Function that generate the pairs below n */
sg_s_pairs(n):=block(
L:makelist([i,2*i+1],i,1,n),
L1:[],
for i from 1 thru length(L) do if map(primep,L[i])=[true,true] then push(L[i],L1),
reverse(L1))$
 
/* Test case */
/* The first of the pairs is a Sophie Germain pair, first element of the pairs must be extracted */
map(first,sg_s_pairs(1500));
</syntaxhighlight>
{{out}}
<pre>
[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]
</pre>
 
=={{header|Nim}}==
<syntaxhighlight lang="Nim">import std/strutils
 
func isPrime(n: Natural): bool =
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var k = 5
var delta = 2
while k * k <= n:
if n mod k == 0: return false
inc k, delta
delta = 6 - delta
result = true
 
iterator sophieGermainPrimes(): int =
var n = 2
while true:
if isPrime(n) and isPrime(2 * n + 1):
yield n
inc n
 
echo "First 50 Sophie Germain primes:"
var count = 0
for n in sophieGermainPrimes():
inc count
stdout.write align($n, 4)
stdout.write if count mod 10 == 0: '\n' else: ' '
if count == 50: break
</syntaxhighlight>
 
{{out}}
<pre>First 50 Sophie Germain primes:
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
</pre>
 
=={{header|PARI/GP}}==
<syntaxhighlight lang="parigp">issg(n)=if(isprime(n)&&isprime(1+2*n),1,0)
c = 0
n = 2
while(c<50,if(issg(n),print(n);c=c+1);n=n+1)</syntaxhighlight>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<lang perl>#!/usr/bin/perl
<syntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Safe_and_Sophie_Germain_primes
Line 76 ⟶ 563:
my @want;
forprimes { is_prime(2 * $_ + 1) and (50 == push @want, $_)
and print("@want\n" =~ s/.{65}\K /\n/gr) + exit } 2, 1e9;</langsyntaxhighlight>
{{out}}
<pre>
Line 85 ⟶ 572:
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">sophie_germain</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
Line 99 ⟶ 586:
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First 50: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">),</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))})</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
First 50: 2 3 5 11 23 ... 1409 1439 1451 1481 1499
</pre>
 
=={{header|Python}}==
<syntaxhighlight lang="python">
print("working...")
row = 0
limit = 1500
Sophie = []
 
def isPrime(n):
for i in range(2,int(n**0.5)+1):
if n%i==0:
return False
return True
 
for n in range(2,limit):
p = 2*n + 1
if isPrime(n) and isPrime(p):
Sophie.append(n)
 
print("Found ",end = "")
print(len(Sophie),end = "")
print(" Safe and Sophie primes.")
 
print(Sophie)
print("done...")
</syntaxhighlight>
{{out}}
<pre>
working...
Found 50 Safe and Sophie primes.
[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]
done...
</pre>
 
=={{header|Quackery}}==
 
<code>isprime</code> is defined at [[Primality by trial division#Quackery]].
 
<syntaxhighlight lang="Quackery"> [ temp put [] 0
[ 1+
dup isprime until
dup 2 * 1+ isprime until
dup dip join
over size temp share = until ]
drop
temp release ] is sgprimes ( n --> [ )
 
50 sgprimes witheach [ echo sp ]</syntaxhighlight>
 
{{out}}
 
<pre>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 </pre>
 
=={{header|Raku}}==
<syntaxhighlight lang="raku" perl6line>put join "\n", (^∞ .grep: { .is-prime && ($_*2+1).is-prime } )[^50].batch(10)».fmt: "%4d";</langsyntaxhighlight>
{{out}}
<pre> 2 3 5 11 23 29 41 53 83 89
Line 113 ⟶ 652:
683 719 743 761 809 911 953 1013 1019 1031
1049 1103 1223 1229 1289 1409 1439 1451 1481 1499</pre>
 
=={{header|Ring}}==
<syntaxhighlight lang="ring">
load "stdlib.ring"
see "working..." +nl
row = 0
limit = 1500
Sophie = []
 
for n = 1 to limit
p = 2*n + 1
if isprime(n) and isprime(p)
add(Sophie,n)
ok
next
 
see "Found " + len(Sophie) + " Safe and Sophie German primes."+nl
 
for n = 1 to len(Sophie)
row++
see "" + Sophie[n] + " "
if row % 10 = 0
see nl
ok
next
 
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
working...
Found 50 Safe and Sophie primes.
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
done...
</pre>
 
=={{header|RPL}}==
{{works with|HP|49g}}
≪ DUP + 1 + ISPRIME?
≫ '<span style="color:blue">SOPHIE?</span>' STO
≪ → function count
≪ { } 2
'''WHILE''' OVER SIZE count < '''REPEAT '''
'''IF''' DUP function EVAL '''THEN''' SWAP OVER + SWAP '''END'''
NEXTPRIME
'''END'''
DROP
≫ ≫ '<span style="color:blue">FIRSTSEQ</span>' STO
 
≪ <span style="color:blue">SOPHIE?</span> ≫ 50 <span style="color:blue">FIRSTSEQ</span>
{{out}
<pre>
1: {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}
</pre>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">^Inf -> lazy.grep{|p| all_prime(p, 2*p + 1) }.first(50).slices(10).each{
.join(', ').say
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
=={{header|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
 
Line 133 ⟶ 742:
}
System.print("The first 50 Sophie Germain primes are:")
for (chunk in Lst.chunks(sgp, 10)) Fmt.printtprint("$,5d", chunksgp, 10)</langsyntaxhighlight>
 
{{out}}
Line 146 ⟶ 755:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">func IsPrime(N); \Return 'true' if N is a prime number
int N, I;
[for I:= 2 to sqrt(N) do
Line 163 ⟶ 772:
N:= N+1;
until Count >= 50;
]</langsyntaxhighlight>
 
{{out}}
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/318372...355290"