Find squares n where n+1 is prime: Difference between revisions
Added Easylang
(Added AppleScript solutions.) |
(Added Easylang) |
||
| (11 intermediate revisions by 4 users not shown) | |||
Line 20:
OD
END</syntaxhighlight>
{{out}}
<pre>
1 4 16 36 100 196 256 400 576 676
</pre>
=={{header|ALGOL W}}==
Using the difference of two squares to optimise the primality tests and the square loop (similar to the Phix and Applescript samples), though with the small number of values to test, that probably doesn't affect runtime much...
<syntaxhighlight lang="algolw">
begin % find squares n where n + 1 is prime %
% returns true if n is prime, false otherwise, uses trial division %
logical procedure isPrime ( integer value n ) ;
if n < 3 then n = 2
else if n rem 3 = 0 then n = 3
else if not odd( n ) then false
else begin
logical prime;
integer f, f2, toNext;
prime := true;
f := 5;
f2 := 25;
toNext := 24; % note: ( 2n + 1 )^2 - ( 2n - 1 )^2 = 8n %
while f2 <= n and prime do begin
prime := n rem f not = 0;
f := f + 2;
f2 := toNext;
toNext := toNext + 8
end while_f2_le_n_and_prime ;
prime
end isPrime ;
% other than 1, the numbers must be even %
if isPrime( 2 % i.e.: ( 1 * 1 ) + 1 % ) then write( ( " 1" ) );
begin
integer i2, toNext;
toNext := i2 := 4; % note: ( 2n + 2 )^2 - 2n^2 = 8n + 4 %
while i2 < 1000 do begin
if isPrime( i2 + 1 ) then writeon( i_w := 1, s_w := 0, " ", i2 );
toNext := toNext + 8;
i2 := i2 + toNext
end while_i2_lt_1000
end
end.
</syntaxhighlight>
{{out}}
<pre>
Line 425 ⟶ 471:
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
n0 = 1
repeat
n = n0 * n0
until n >= 1000
if isprim (n + 1) = 1
write n & " "
.
n0 += 1
.
</syntaxhighlight>
{{out}}
<pre>
1 4 16 36 100 196 256 400 576 676
</pre>
=={{header|F_Sharp|F#}}==
Line 548 ⟶ 621:
576
676
</pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">
module Squares
where
isPrime :: Int -> Bool
isPrime n
|n == 2 = True
|n == 1 = False
|otherwise = null $ filter (\i -> mod n i == 0 ) [2 .. root]
where
root :: Int
root = floor $ sqrt $ fromIntegral n
isSquare :: Int -> Bool
isSquare n = theFloor * theFloor == n
where
theFloor :: Int
theFloor = floor $ sqrt $ fromIntegral n
solution :: [Int]
solution = [d | d <- [1..999] , isSquare d && isPrime ( d + 1 )]
</syntaxhighlight>
{{out}}
<pre>
[1,4,16,36,100,196,256,400,576,676]
</pre>
Line 833 ⟶ 934:
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">},</span><span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1000</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)}),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
=={{header|PL/M}}==
{{Trans|ALGOL W}}
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
<syntaxhighlight lang="plm">
100H: /* FIND SQUARES N WHERE N + ! IS PRIME */
/* CP/M BDOS SYSTEM CALL AND I/O ROUTINES */
BDOS: PROCEDURE( FN, ARG ); DECLARE FN BYTE, ARG ADDRESS; GOTO 5; END;
PR$CHAR: PROCEDURE( C ); DECLARE C BYTE; CALL BDOS( 2, C ); END;
PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
PR$NL: PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH ); END;
PR$NUMBER: PROCEDURE( N ); /* PRINTS A NUMBER IN THE MINIMUN FIELD WIDTH */
DECLARE N ADDRESS;
DECLARE V ADDRESS, N$STR ( 6 )BYTE, W BYTE;
V = N;
W = LAST( N$STR );
N$STR( W ) = '$';
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
DO WHILE( ( V := V / 10 ) > 0 );
N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
END;
CALL PR$STRING( .N$STR( W ) );
END PR$NUMBER;
/* RETURNS TRUE IF N IS PRIME, FALSE OTHERWISE, USES TRIAL DIVISION */
IS$PRIME: PROCEDURE( N )BYTE;
DECLARE N ADDRESS;
DECLARE PRIME BYTE;
IF N < 3 THEN PRIME = N = 2;
ELSE IF N MOD 3 = 0 THEN PRIME = N = 3;
ELSE IF N MOD 2 = 0 THEN PRIME = 0;
ELSE DO;
DECLARE ( F, F2, TO$NEXT ) ADDRESS;
PRIME = 1;
F = 5;
F2 = 25;
TO$NEXT = 24; /* NOTE: ( 2N + 1 )^2 - ( 2N - 1 )^2 = 8N */
DO WHILE F2 <= N AND PRIME;
PRIME = N MOD F <> 0;
F = F + 2;
F2 = F2 + TO$NEXT;
TO$NEXT = TO$NEXT + 8;
END;
END;
RETURN PRIME;
END IS$PRIME;
/* TASK */
/* OTHER THAN 1, THE NUMBERS MUST BE EVEN */
IF IS$PRIME( 2 /* I.E.: ( 1 * 1 ) + 1 */ ) THEN DO;
CALL PR$CHAR( ' ' );
CALL PR$CHAR( '1' );
END;
DECLARE ( I2, TO$NEXT ) ADDRESS;
TO$NEXT, I2 = 4; /* NOTE: ( 2N + 2 )^2 - 2N^2 = 8N + 4 */
DO WHILE I2 < 1000;
IF IS$PRIME( I2 + 1 ) THEN DO;
CALL PR$CHAR( ' ' );
CALL PR$NUMBER( I2 );
END;
TO$NEXT = TO$NEXT + 8;
I2 = I2 + TO$NEXT;
END;
EOF
</syntaxhighlight>
{{out}}
<pre>
1 4 16 36 100 196 256 400 576 676
</pre>
=={{header|PROMAL}}==
{{Trans|ALGOL W}}
<syntaxhighlight lang="promal">
;;; Find squares n where n + 1 is prime
PROGRAM primesq
INCLUDE library
;;; returns TRUE(1) if p is prime, FALSE(0) otherwise
FUNC BYTE isPrime
ARG WORD n
WORD i
WORD f
WORD f2
WORD toNext
BYTE prime
BEGIN
IF n < 3
prime = n = 2
ELSE IF n % 3 = 0
prime = n = 3
ELSE IF n % 2 = 0
prime = 0
ELSE
prime = 1
f = 5
f2 = 25
toNext = 24 ; note: ( 2n + 1 )^2 - ( 2n - 1 )^2 = 8n
WHILE f2 <= n AND prime
prime = n % f <> 0
f = f + 2
f2 = toNext
toNext = toNext + 8
RETURN prime
END
WORD i2
WORD toNext
BEGIN
IF isPrime( ( 1 * 1 ) + 1 ) ; 1 is the only possible odd number
OUTPUT " 1"
i2 = 4
toNext = 4 ; note: ( 2n + 2 )^2 - 2n^2 = 8n + 4
WHILE i2 < 1000
IF isPrime( i2 + 1 )
OUTPUT " #W", i2
toNext = toNext + 8
i2 = i2 + toNext
END
</syntaxhighlight>
{{out}}
<pre>
1 4 16 36 100 196 256 400 576 676
</pre>
=={{header|Python}}==
Line 864 ⟶ 1,094:
done...
</pre>
=={{header|Quackery}}==
<code>isprime</code> is defined at [[Primality by trial division#Quackery]].
<syntaxhighlight lang="Quackery"> [] [] 0
[ 1+ dup 2 **
dup 1000 < while
1+ isprime if
[ dup dip join ]
again ]
2drop
witheach [ 2 ** join ]
echo</syntaxhighlight>
{{out}}
<pre>[ 1 4 16 36 100 196 256 400 576 676 ]</pre>
=={{header|Racket}}==
Line 973 ⟶ 1,221:
{{out}}
<pre>
[1, 4, 16, 36, 100, 196, 256, 400, 576, 676]
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use primes::is_prime ;
fn is_square( number : u64 ) -> bool {
let floor : u64 = (number as f64).sqrt( ).floor( ) as u64 ;
floor * floor == number
}
fn main() {
let solution : Vec<u64> = (1..1000).into_iter( ).
filter( | d | is_square( *d ) && is_prime( *d + 1 )).collect( ) ;
println!("{:?}" , solution);
}
</syntaxhighlight>
{{out}}<pre>
[1, 4, 16, 36, 100, 196, 256, 400, 576, 676]
</pre>
Line 1,011 ⟶ 1,278:
576
676</pre>
=={{header|VTL-2}}==
{{Trans|TinyBASIC}}
<syntaxhighlight lang="vtl2">
1000 ?=1
1010 N=2
1020 M=4
1030 J=M+1
1040 #=2000
1050 #=P=1=0*1080
1060 $=32
1070 ?=M
1080 N=N+2
1090 M=N*N
1100 #=M<1000*1030
1110 #=9999
2000 R=!
2010 P=0
2020 I=3
2030 #=J/I*0+%=0*R
2040 I=I+2
2050 #=I*I<J*2030
2060 P=1
2070 #=R
</syntaxhighlight>
{{out}}
<pre>
1 4 16 36 100 196 256 400 576 676
</pre>
=={{header|Wren}}==
{{libheader|Wren-math}}
<syntaxhighlight lang="
var squares = []
| |||