Safe and Sophie Germain primes: Difference between revisions
Content deleted Content added
Added Easylang |
No edit summary |
||
(18 intermediate revisions by 4 users not shown) | |||
Line 39:
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|8080 Assembly}}==
<syntaxhighlight lang="asm">NPRIMES equ 3000
org 100h
lxi b,NPRIMES
lxi h,primes
mvi e,0
zerolp: mov m,e
inx h
dcx b
mov a,b
ora c
jnz zerolp
lxi b,-NPRIMES
lxi d,2
sieve: mov h,d
mov l,e
sieve2: dad d
push h
lxi b,primes
dad b
inr m
pop h
push h
lxi b,-NPRIMES
dad b
pop h
jnc sieve2
inx d
mov h,d
mov l,e
dad b
jnc sieve
lxi b,50*256+5
lxi d,1
search: inx d
lxi h,primes
dad d
mov a,m
ora a
jnz search
mov h,d
mov l,e
dad d
inx h
push b
lxi b,primes
dad b
pop b
mov a,m
ora a
jnz search
push d
push b
lxi h,buf
push h
lxi b,-10
itoa: xchg
lxi d,-1
digit: inx d
dad b
jc digit
mvi a,'0'+10
add l
pop h
dcx h
mov m,a
push h
mov a,d
ora e
jnz itoa
pop d
mvi c,9
call 5
pop b
dcr c
push b
jz prnl
mvi e,9
mvi c,2
call 5
pop b
jmp next
prnl: lxi d,nl
mvi c,9
call 5
pop b
mvi c,5
next: pop d
dcr b
jnz search
ret
db '.....'
buf: db '$'
nl: db 13,10,'$'
primes: equ $</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|ABC}}==
<syntaxhighlight lang="abc">HOW TO REPORT prime n:
IF n<2: FAIL
REPORT NO d IN {2..floor (root n)} HAS n mod d = 0
HOW TO REPORT sophie.germain.prime n:
REPORT prime n AND prime (2*n + 1)
PUT 50 IN amount
PUT 1 IN n
WHILE amount > 0:
WHILE NOT sophie.germain.prime n: PUT n+1 IN n
WRITE n >> 6
IF amount mod 10 = 1: WRITE /
PUT amount-1 IN amount
PUT n+1 IN n</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}}==
Line 63 ⟶ 193:
1481 1499
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">5 10⍴(⊢(/⍨)⊢∊⍨1+2×⊢) ((⊢(/⍨)⊢(~∊)∘.×⍨) 1↓⍳) 3000</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|Arturo}}==
Line 127 ⟶ 267:
1049 1103 1223 1229 1289 1409 1439 1451 1481 1499
</pre>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">Prime ← (2≤⊢)∧(¬0⊑∘∊(1↓1+↕∘⌊∘√)⊸|)
Sophie ← Prime ∧ (Prime 1+2×⊢)
•Show 5‿10⥊Sophie¨⊸/↕3000</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|C}}==
<syntaxhighlight lang="c">#include <stdbool.h>
#include <stdio.h>
bool prime(unsigned n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
if (n % 3 == 0) return n == 3;
for (unsigned d = 5; d*d <= n; d += 4) {
if (n % d == 0) return false;
d += 2;
if (n % d == 0) return false;
}
return true;
}
bool sophie_germain(unsigned n) {
return prime(n) && prime(2*n + 1);
}
int main(void) {
unsigned n = 0;
for (int amount = 50; amount > 0; amount--) {
do { n++; } while (!sophie_germain(n));
printf("%-6u", n);
if (amount % 10 == 1) printf("\n");
}
return 0;
}</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|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
sub prime(n: uint16): (r: uint8) is
if n<2 then r := 0; return; end if;
if n==2 then r := 1; return; end if;
if n%2==0 then r := 0; return; end if;
var d: uint16 := 3;
while d*d <= n loop
if n%d == 0 then r := 0; return; end if
d := d + 2;
end loop;
r := 1;
end sub;
sub sophie_germain(n: uint16): (r: uint8) is
r := 0;
if prime(n) != 0 and prime(2*n+1) != 0 then
r := 1;
end if;
end sub;
var n: uint16 := 1;
var amount: uint16 := 50;
while amount > 0 loop
if sophie_germain(n) != 0 then
print_i16(n);
if amount % 10 == 1
then print_nl();
else print_char('\t');
end if;
amount := amount - 1;
end if;
n := n + 1;
end loop;
print_nl();</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|Delphi}}==
Line 193 ⟶ 424:
</pre>
=={{header|Draco}}==
<syntaxhighlight>proc prime(word n) bool:
word d;
bool is_prime;
if n<2 then false
elif n%2 = 0 then n=2
elif n%3 = 0 then n=3
else
d := 5;
is_prime := true;
while
is_prime and d*d <= n
do
is_prime := is_prime and n % d /= 0;
d := d + 2;
is_prime := is_prime and n % d /= 0;
d := d + 4
od;
is_prime
fi
corp
proc sophie(word n) bool:
prime(n) and prime(2*n + 1)
corp
proc main() void:
word n, i;
n := 0;
for i from 1 upto 50 do
while n := n + 1; not sophie(n) do od;
write(n:6);
if i % 10 = 0 then writeln() fi
od
corp</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|EasyLang}}==
<syntaxhighlight lang=text>
fastfunc isprim num .
i = 2
Line 457 ⟶ 729:
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|Haskell}}==
<syntaxhighlight lang="haskell">isPrime :: Int -> Bool
isPrime n
|n == 2 = True
|otherwise = all (\i -> mod n i /= 0 ) [2..limit]
where
limit = floor $ sqrt $ fromIntegral n
solution :: [Int]
solution = take 50 $ filter (\i -> isPrime i && isPrime ( 2 * i + 1 ) ) [2 , 3 ..]
</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>
Line 500 ⟶ 788:
1049 1103 1223 1229 1289 1409 1439 1451 1481 1499
</pre>
=={{header|MAD}}==
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
INTERNAL FUNCTION(X)
ENTRY TO PRIME.
WHENEVER X.L.2, FUNCTION RETURN 0B
WHENEVER X.E.X/2*2, FUNCTION RETURN X.E.2
WHENEVER X.E.X/3*3, FUNCTION RETURN X.E.3
D = 5
TEST WHENEVER D*D.G.X, FUNCTION RETURN 1B
WHENEVER X.E.X/D*D, FUNCTION RETURN 0B
D = D+2
WHENEVER X.E.X/D*D, FUNCTION RETURN 0B
D = D+4
TRANSFER TO TEST
END OF FUNCTION
INTERNAL FUNCTION(X)
ENTRY TO SOPHIE.
WHENEVER .NOT. PRIME.(X), FUNCTION RETURN 0B
FUNCTION RETURN PRIME.(X*2+1)
END OF FUNCTION
DIMENSION LINE(10)
VECTOR VALUES LINFMT = $10(I6)*$
COL = 0
N = 0
THROUGH LOOP, FOR I=50, -1, I.E.0
SEARCH THROUGH SEARCH, FOR N=N+1, 1, SOPHIE.(N)
LINE(COL) = N
COL = COL + 1
WHENEVER COL.E.10
COL = 0
PRINT FORMAT LINFMT,LINE(0),LINE(1),LINE(2),
0 LINE(3),LINE(4),LINE(5),LINE(6),LINE(7),
1 LINE(8),LINE(9)
LOOP END OF CONDITIONAL
END OF PROGRAM</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|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">nextSafe[n_] :=
Line 533 ⟶ 866:
[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|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (table 6 10 (take 50 sophie))]
table :: num->num->[num]->[char]
table cw w ls = lay [concat [rjustify cw (show n) | n<-part] | part<-split w ls]
split :: num->[*]->[[*]]
split n [] = []
split n ls = take n ls:split n (drop n ls)
sophie :: [num]
sophie = [p | p<-primes; (2*p+1) $in primes]
primes :: [num]
primes = sieve [2..] where sieve (p:ns) = p : sieve [n | n<-ns; n mod p>0]
in :: *->[*]->bool
in a [] = False
in a (a:as) = True
in b (a:as) = False, if a>b
in b (a:as) = b $in as</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|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE SophieGermainPrimes;
FROM InOut IMPORT WriteCard, WriteLn;
VAR n, i: CARDINAL;
PROCEDURE prime(n: CARDINAL): BOOLEAN;
VAR d: CARDINAL;
BEGIN
IF n<2 THEN RETURN FALSE END;
IF n MOD 2=0 THEN RETURN n=2 END;
IF n MOD 3=0 THEN RETURN n=3 END;
d := 5;
WHILE d*d <= n DO
IF n MOD d=0 THEN RETURN FALSE END;
INC(d, 2);
IF n MOD d=0 THEN RETURN FALSE END;
INC(d, 4)
END;
RETURN TRUE
END prime;
PROCEDURE sophieGermain(n: CARDINAL): BOOLEAN;
BEGIN
RETURN prime(n) AND prime(2*n + 1)
END sophieGermain;
BEGIN
n := 0;
FOR i := 1 TO 50 DO
REPEAT INC(n) UNTIL sophieGermain(n);
WriteCard(n, 6);
IF i MOD 10 = 0 THEN WriteLn END
END
END SophieGermainPrimes.</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}}==
Line 579 ⟶ 983:
n = 2
while(c<50,if(issg(n),print(n);c=c+1);n=n+1)</syntaxhighlight>
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
##
uses school;
var primenumbers := firstprimes(1000);
primes(3000).where(x -> 2 * x + 1 in primenumbers).take(50).println;
</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|Perl}}==
Line 618 ⟶ 1,035:
First 50: 2 3 5 11 23 ... 1409 1439 1451 1481 1499
</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pli">sophieGermainPrimes: procedure options(main);
prime: procedure(n) returns(bit);
declare (n, d) fixed;
if n<=4 then return(n=2 | n=3);
if mod(n,2)=0 | mod(n,3)=0 then return('0'b);
do d=5 repeat(d+4) while(d*d<=n);
if mod(n,d)=0 then return('0'b);
d = d+2;
if mod(n,d)=0 then return('0'b);
end;
return('1'b);
end prime;
sophie: procedure(n) returns(bit);
declare n fixed;
return(prime(n) & prime(n*2+1));
end sophie;
declare (n, i) fixed;
n = 0;
do i=1 to 50;
do n=n+1 repeat(n+1) while(^sophie(n)); end;
put edit(n) (F(6));
if mod(i, 10)=0 then put skip;
end;
end sophieGermainPrimes;</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|PL/M}}==
<syntaxhighlight lang="plm">100H:
BDOS: PROCEDURE (FN,ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; GO TO 0; END EXIT;
PUTCH: PROCEDURE (CHAR); DECLARE CHAR BYTE; CALL BDOS(2, CHAR); END PUTCH;
PUTS: PROCEDURE (STR); DECLARE STR ADDRESS; CALL BDOS(9, STR); END PUTS;
DECLARE FALSE LITERALLY '0', TRUE LITERALLY 'NOT FALSE';
PRINT$NUM: PROCEDURE (N);
DECLARE (N, P) ADDRESS, S (6) BYTE INITIAL ('.....$');
DECLARE DGT BASED P BYTE;
P = .S(5);
DIGIT:
P = P-1;
DGT = N MOD 10 + '0';
IF (N := N/10) > 0 THEN GO TO DIGIT;
CALL PUTS(P);
END PRINT$NUM;
PRIME: PROCEDURE (N) BYTE;
DECLARE (N, D) ADDRESS;
IF N<=4 THEN RETURN N=2 OR N=3;
IF NOT N OR N MOD 3=0 THEN RETURN FALSE;
D = 5;
DO WHILE D*D <= N;
IF N MOD D=0 THEN RETURN FALSE;
D = D+2;
IF N MOD D=0 THEN RETURN FALSE;
D = D+4;
END;
RETURN TRUE;
END PRIME;
SOPHIE$GERMAIN: PROCEDURE (N) BYTE;
DECLARE N ADDRESS;
RETURN PRIME(N) AND PRIME(N+N+1);
END SOPHIE$GERMAIN;
DECLARE I BYTE, N ADDRESS INITIAL (0);
DO I=1 TO 50;
DO WHILE NOT SOPHIE$GERMAIN(N := N+1); END;
CALL PRINT$NUM(N);
IF I MOD 5=0
THEN CALL PUTS(.(13,10,'$'));
ELSE CALL PUTCH(9);
END;
CALL EXIT;
EOF</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|Python}}==
Line 679 ⟶ 1,192:
683 719 743 761 809 911 953 1013 1019 1031
1049 1103 1223 1229 1289 1409 1439 1451 1481 1499</pre>
=={{header|Refal}}==
<syntaxhighlight>$ENTRY Go {
= <Table (10 6) <Gen 50 SophieGermain>>;
};
Cell {
s.CW s.N, <Repeat s.CW ' '> <Symb s.N>: e.R,
<Last s.CW e.R>: (e.X) e.C = e.C;
};
Repeat {
0 s.I = ;
s.N s.I = s.I <Repeat <- s.N 1> s.I>;
};
Table {
(s.W s.CW) = ;
(s.W s.CW) e.X, <First s.W e.X>: (e.Row) e.Rest =
<Prout <Each (Cell s.CW) e.Row>>
<Table (s.W s.CW) e.Rest>;
};
Gen {
s.N s.F = <Gen s.N s.F 1>;
0 s.F s.I = ;
s.N s.F s.I, <Mu s.F s.I>: {
True = s.I <Gen <- s.N 1> s.F <+ s.I 1>>;
False = <Gen s.N s.F <+ s.I 1>>;
};
};
SophieGermain {
s.N, <+ 1 <* 2 s.N>>: s.Safe = <And <Prime s.N> <Prime s.Safe>>;
};
Prime {
s.N, <Compare s.N 2>: '-' = False;
s.N = <Prime s.N 2>;
s.N s.D, <Compare s.N <* s.D s.D>>: '-' = True;
s.N s.D, <Mod s.N s.D>: 0 = False;
s.N s.D = <Prime s.N <+ s.D 1>>;
};
And {
True True = True;
s.X s.Y = False;
};
Each {
(e.F) = ;
(e.F) s.I e.X = <Mu e.F s.I> <Each (e.F) e.X>;
};</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|Ring}}==
Line 739 ⟶ 1,311:
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">fn is_prime( num : u32 ) -> bool {
let limit : u32 = (num as f32).sqrt( ).floor( ) as u32 ;
(2..=limit).all( | x | num % x != 0 )
}
fn main() {
let mut sophie_primes : Vec<u32> = Vec::new( ) ;
let mut count : u8 = 0 ;
let mut current : u32 = 2 ;
while count < 50 {
if is_prime( current ) && is_prime( 2 * current + 1 ) {
sophie_primes.push( current ) ;
count += 1 ;
}
current += 1 ;
}
println!("The first 50 Sophie - Germain primes:" ) ;
let mut ct : u8 = 0 ;
for num in sophie_primes {
print!("{:>5}" , num ) ;
ct += 1 ;
if ct % 10 == 0 {
println!("") ;
ct = 0 ;
}
}
}</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|SETL}}==
<syntaxhighlight lang="setl">program sophie_germain_primes;
amount := 50;
loop until amount = 0 do
if sophie (n +:= 1) then
nprint(lpad(str n, 6));
amount -:= 1;
if amount mod 10=0 then print; end if;
end if;
end loop;
op sophie(n);
return prime n and prime (2*n+1);
end op;
op prime(n);
if n<5 then return n in {2,3}; end if;
if n mod 2=0 or n mod 3=0 then return false; end if;
d := 5;
loop while d*d <= n do
if n mod d=0 then return false; end if;
d +:= 2;
if n mod d=0 then return false; end if;
d +:= 4;
end loop;
return true;
end op;
end program;</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|Sidef}}==
<syntaxhighlight lang="ruby">^Inf -> lazy.grep{|p| all_prime(p, 2*p + 1) }.first(50).slices(10).each{
Line 751 ⟶ 1,396:
1049, 1103, 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499
</pre>
=={{header|VTL-2}}==
<syntaxhighlight lang="vtl2">10 Z=3000
20 I=0
30 I=I+1
40 :I)=0
50 #=I=Z=0*30
60 I=2
70 J=I+I
80 :J)=1
90 J=J+I
100 #=J>Z=0*80
110 I=I+1
120 #=I>Z=0*70
130 N=1
140 I=50
150 N=N+1
160 #=:N)+:N+N+1)>1*150
170 ?=N
180 I=I-1
190 #=I=0*999
200 #=I/5*0=%*230
210 ?=9
220 #=150
230 ?=""
240 #=150</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}}==
|