Safe and Sophie Germain primes: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Safe and Sophie Germain primes in various BASIC dialents) |
m (→{{header|Wren}}: Minor tidy) |
||
(13 intermediate revisions by 12 users not shown) | |||
Line 2:
[[Category:Mathematics]]
A prime number ''p'' is
The number 2''p'' + 1 associated with a Sophie Germain prime is called a '''safe prime'''.
;Task
Generate the first '''50''' 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}}==
<
I a == 2
R 1B
Line 26 ⟶ 33:
I ++cnt == 50
L.break
print()</
{{out}}
Line 35 ⟶ 42:
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-primes}}
<
PR read "primes.incl.a68" PR
[]BOOL prime = PRIMESIEVE 10 000; # hopefully, enough primes #
Line 47 ⟶ 54:
FI
OD
END</
{{out}}
<pre>
Line 56 ⟶ 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 {
Line 85 ⟶ 117:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 94 ⟶ 126:
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}}==
<
n:=3;
!!2;
Line 106 ⟶ 220:
fi;
n:+2;
od;</
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
<
if n < 2 then return false
if n < 4 then return true
Line 136 ⟶ 250:
if c mod 10 = 0 then print
end if
wend</
{{out}}<pre>2 3 5 11 23 29 41 53 83 89
113 131 173 179 191 233 239 251 281 293
Line 144 ⟶ 258:
==={{header|GW-BASIC}}===
<
20 C = 1
30 N = 3
Line 172 ⟶ 286:
270 WEND
280 Z = 1
290 RETURN</
==={{header|BASIC256}}===
<
if v < 2 then return False
if v mod 2 = 0 then return v = 2
Line 202 ⟶ 316:
end if
end while
end</
==={{header|PureBasic}}===
<
If v <= 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
Line 242 ⟶ 356:
Wend
Input()
CloseConsole()</
==={{header|Yabasic}}===
<
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
Line 272 ⟶ 386:
endif
wend
end</
=={{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 280 ⟶ 447:
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.
<
{{out}}
<pre>
Line 293 ⟶ 460:
=={{header|Julia}}==
<
for (i, p) in enumerate(filter(x -> isprime(2x + 1), primes(1500)))
print(lpad(p, 5), i % 10 == 0 ? "\n" : "")
end
</
<pre>
2 3 5 11 23 29 41 53 83 89
Line 307 ⟶ 474:
</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
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]</
{{out}}<pre>
Line 320 ⟶ 487:
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}}==
<
c = 0
n = 2
while(c<50,if(issg(n),print(n);c=c+1);n=n+1)</
=={{header|Perl}}==
{{libheader|ntheory}}
<
use strict; # https://rosettacode.org/wiki/Safe_and_Sophie_Germain_primes
Line 338 ⟶ 563:
my @want;
forprimes { is_prime(2 * $_ + 1) and (50 == push @want, $_)
and print("@want\n" =~ s/.{65}\K /\n/gr) + exit } 2, 1e9;</
{{out}}
<pre>
Line 347 ⟶ 572:
=={{header|Phix}}==
<!--<
<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 361 ⟶ 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>
<!--</
{{out}}
<pre>
Line 368 ⟶ 593:
=={{header|Python}}==
<
print("working...")
row = 0
Line 391 ⟶ 616:
print(Sophie)
print("done...")
</syntaxhighlight>
{{out}}
<pre>
Line 399 ⟶ 624:
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"
{{out}}
<pre> 2 3 5 11 23 29 41 53 83 89
Line 410 ⟶ 654:
=={{header|Ring}}==
<
load "stdlib.ring"
see "working..." +nl
Line 435 ⟶ 679:
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 446 ⟶ 690:
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-fmt}}
<
import "./fmt" for Fmt
Line 467 ⟶ 742:
}
System.print("The first 50 Sophie Germain primes are:")
{{out}}
Line 480 ⟶ 755:
=={{header|XPL0}}==
<
int N, I;
[for I:= 2 to sqrt(N) do
Line 497 ⟶ 772:
N:= N+1;
until Count >= 50;
]</
{{out}}
|