Safe and Sophie Germain primes: Difference between revisions

← Older edit

Safe and Sophie Germain primes (view source)

Revision as of 10:06, 4 February 2024

9,592 bytes added , 3 months ago

m

→‎{{header|Wren}}: Minor tidy

PureFox

9,476

edits

Revision as of 00:11, 12 January 2022 (view source) Alextretyak (talk \| contribs) (Added 11l) ← Older edit		Latest revision as of 10:06, 4 February 2024 (view source) PureFox (talk \| contribs) m (→‎{{header\|Wren}}: Minor tidy)
(14 intermediate revisions by 13 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'' + 1 is also prime.<br> ~~;<b>See the same at [[Safe_primes_and_unsafe_primes]]</b><br>~~ 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}}== <~~lang~~syntaxhighlight lang="11l">F is_prime(a) I a == 2 R 1B Line 26 ⟶ 33: I ++cnt == 50 L.break print()</~~lang~~syntaxhighlight> {{out}} Line 35 ⟶ 42: =={{header\|ALGOL 68}}== {{libheader\|ALGOL 68-primes}} <~~lang~~syntaxhighlight 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 47 ⟶ 54: FI OD END</~~lang~~syntaxhighlight> {{out}} <pre> Line 56 ⟶ 63: 1481 1499 </pre> =={{header\|Arturo}}== <syntaxhighlight lang="rebol">sophieG?: function [p][ and? [prime? p][prime? 1 + 2p] ] 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"> ~~<lang AWK>~~ # syntax: GAWK -f SAFE_AND_SOPHIE_GERMAIN_PRIMES.AWK BEGIN { Line 85 ⟶ 117: return(1) } </syntaxhighlight> ~~</lang>~~ {{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}}== <~~lang~~syntaxhighlight lang="fermat">c:=1; n:=3; !!2; Line 106 ⟶ 220: fi; n:+2; od;</~~lang~~syntaxhighlight> =={{header\|~~FreeBASIC~~BASIC}}== ==={{header\|FreeBASIC}}=== ~~<lang freebasic>function isprime(n as integer) as boolean~~ <syntaxhighlight lang="freebasic">function isprime(n as integer) as boolean if n < 2 then return false if n < 4 then return true Line 135 ⟶ 250: if c mod 10 = 0 then print end if wend</~~lang~~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> ~~</pre>~~ ==={{header\|GW-BASIC}}=== <~~lang~~syntaxhighlight lang="gwbasic">10 PRINT "2 "; 20 C = 1 30 N = 3 Line 172 ⟶ 286: 270 WEND 280 Z = 1 290 RETURN</~~lang~~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(2n+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(2n+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(2n+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(2p+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 180 ⟶ 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. <~~lang~~syntaxhighlight lang="jq">limit(50; primes \| select(2. + 1\|is_prime))</~~lang~~syntaxhighlight> {{out}} <pre> Line 193 ⟶ 460: =={{header\|Julia}}== <~~lang~~syntaxhighlight 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~~syntaxhighlight>{{out}} <pre> 2 3 5 11 23 29 41 53 83 89 Line 207 ⟶ 474: </pre> =={{header\|Mathematica}} / {{header\|Wolfram Language}}== <~~lang~~syntaxhighlight ~~Mathematica~~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]</~~lang~~syntaxhighlight> {{out}}<pre> Line 220 ⟶ 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,2i+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}}== <~~lang~~syntaxhighlight lang="parigp">issg(n)=if(isprime(n)&&isprime(1+2n),1,0) c = 0 n = 2 while(c<50,if(issg(n),print(n);c=c+1);n=n+1)</~~lang~~syntaxhighlight> =={{header\|Perl}}== {{libheader\|ntheory}} <~~lang~~syntaxhighlight lang="perl">#!/usr/bin/perl use strict; # https://rosettacode.org/wiki/Safe_and_Sophie_Germain_primes Line 238 ⟶ 563: my @want; forprimes { is_prime(2 $_ + 1) and (50 == push @want, $_) and print("@want\n" =~ s/.{65}\K /\n/gr) + exit } 2, 1e9;</~~lang~~syntaxhighlight> {{out}} <pre> Line 247 ⟶ 572: =={{header\|Phix}}== <!--<~~lang~~syntaxhighlight ~~Phix~~lang="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 261 ⟶ 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> <!--</~~lang~~syntaxhighlight>--> {{out}} <pre> Line 268 ⟶ 593: =={{header\|Python}}== <~~lang~~syntaxhighlight lang="python"> print("working...") row = 0 Line 291 ⟶ 616: print(Sophie) print("done...") </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 299 ⟶ 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" ~~perl6~~line>put join "\n", (^∞ .grep: { .is-prime && ($_2+1).is-prime } )[^50].batch(10)».fmt: "%4d";</~~lang~~syntaxhighlight> {{out}} <pre> 2 3 5 11 23 29 41 53 83 89 Line 310 ⟶ 654: =={{header\|Ring}}== <~~lang~~syntaxhighlight lang="ring"> load "stdlib.ring" see "working..." +nl Line 335 ⟶ 679: see "done..." + nl </syntaxhighlight> ~~</lang>~~ {{out}} <pre> Line 346 ⟶ 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, 2p + 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}} <~~lang~~syntaxhighlight ~~ecmascript~~lang="wren">import "./math" for Int ~~import "./seq" for Lst~~ import "./fmt" for Fmt Line 367 ⟶ 742: } System.print("The first 50 Sophie Germain primes are:") ~~for (chunk in Lst.chunks(sgp, 10))~~ Fmt.~~print~~tprint("$,5d", ~~chunk~~sgp, 10)</~~lang~~syntaxhighlight> {{out}} Line 380 ⟶ 755: =={{header\|XPL0}}== <~~lang~~syntaxhighlight ~~XPL0~~lang="xpl0">func IsPrime(N); \Return 'true' if N is a prime number int N, I; [for I:= 2 to sqrt(N) do Line 397 ⟶ 772: N:= N+1; until Count >= 50; ]</~~lang~~syntaxhighlight> {{out}}