Find prime n such that reversed n is also prime: Difference between revisions
Frink |
Added Sidef |
||
Line 1,336: | Line 1,336: | ||
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 |
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 |
||
Found 34 reverse primes < 500. |
Found 34 reverse primes < 500. |
||
</pre> |
|||
=={{header|Sidef}}== |
|||
<lang ruby>say primes(500).grep { .reverse.is_prime }</lang> |
|||
{{out}} |
|||
<pre> |
|||
[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, 149, 151, 157, 167, 179, 181, 191, 199, 311, 313, 337, 347, 353, 359, 373, 383, 389] |
|||
</pre> |
</pre> |
||
Revision as of 19:53, 9 April 2022
- Task
Find prime n for 0 < n < 500 which are also primes when the (decimal) digits are reversed.
11l
<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
L(n) 1..499
I is_prime(n) & is_prime(Int(reversed(String(n)))) print(n, end' ‘ ’)</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Action!
<lang Action!>INCLUDE "H6:SIEVE.ACT"
BYTE FUNC IsPrimeAndItsReverse(INT i BYTE ARRAY primes)
INT rev BYTE d
IF primes(i)=0 THEN RETURN (0) FI rev=0 WHILE i#0 DO d=i MOD 10 rev==*10 rev==+d i==/10 OD
RETURN (primes(rev))
PROC Main()
DEFINE MAX="999" BYTE ARRAY primes(MAX+1) INT i,count=[0]
Put(125) PutE() ;clear the screen Sieve(primes,MAX+1) FOR i=2 TO 499 DO IF IsPrimeAndItsReverse(i,primes) THEN PrintI(i) Put(32) count==+1 FI OD PrintF("%E%EThere are %I primes",count)
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 There are 34 primes
Ada
<lang Ada>with Ada.Text_Io;
procedure Reverse_Prime is
type Number is new Long_Integer range 0 .. Long_Integer'Last; package Number_Io is new Ada.Text_Io.Integer_Io (Number);
function Is_Prime (A : Number) return Boolean is D : Number; begin if A < 2 then return False; end if; if A in 2 .. 3 then return True; end if; if A mod 2 = 0 then return False; end if; if A mod 3 = 0 then return False; end if; D := 5; while D * D <= A loop if A mod D = 0 then return False; end if; D := D + 2; if A mod D = 0 then return False; end if; D := D + 4; end loop; return True; end Is_Prime;
function Reverse_Num (N : Number) return Number is N2 : Number := N; Res : Number := 0; begin while N2 /= 0 loop Res := 10 * Res; Res := Res + (N2 mod 10); N2 := N2 / 10; end loop; return Res; end Reverse_Num;
use Ada.Text_Io; Count : Natural := 0;
begin
for N in Number range 1 .. 499 loop if Is_Prime (N) and then Is_Prime (Reverse_Num (N)) then Count := Count + 1; Number_Io.Put (N, Width => 3); Put (" "); if Count mod 8 = 0 then New_Line; end if; end if; end loop; New_Line; Put_Line (Count'Image & " primes.");
end Reverse_Prime;</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 34 primes.
ALGOL W
<lang algolw>begin % find some primes whose digits reversed is also prime %
% sets p( 1 :: n ) to a sieve of primes up to n % procedure Eratosthenes ( logical array p( * ) ; integer value n ) ; begin p( 1 ) := false; p( 2 ) := true; for i := 3 step 2 until n do p( i ) := true; for i := 4 step 2 until n do p( i ) := false; for i := 3 step 2 until truncate( sqrt( n ) ) do begin integer ii; ii := i + i; if p( i ) then for pr := i * i step ii until n do p( pr ) := false end for_i ; end Eratosthenes ; integer MAX_NUMBER, maxPrime; MAX_NUMBER := 500; % approximate the largest prime we need to consider ( 10 ^ number of digits in MAX_NUMBER ) % begin integer v; v := MAX_NUMBER; maxPrime := 1; while v > 0 do begin v := v div 10; maxPrime := maxPrime * 10 end while_v_gt_0 end; begin logical array prime( 1 :: maxPrime); integer pCount; % sieve the primes to maxPrime % Eratosthenes( prime, maxPrime ); % find the primes that are reversable % pCount := 0; for i := 1 until MAX_NUMBER - 1 do begin if prime( i ) then begin integer pReversed, v; v := i; pReversed := 0; while v > 0 do begin pReversed := ( pReversed * 10 ) + v rem 10; v := v div 10 end while_v_gt_0 ; if prime( pReversed ) then begin writeon( i_w := 4, s_w := 0, " ", i ); pCount := pCount + 1; if pCount rem 20 = 0 then write() end if_prime_pReversed end if_prime_i end for_i ; write( i_w := 1, s_w := 0, "Found ", pCount, " reversable primes below ", MAX_NUMBER ) end
end.</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 Found 34 reversable primes below 500
AWK
<lang AWK>
- syntax: GAWK -f FIND_PRIME_N_FOR_THAT_REVERSED_N_IS_ALSO_PRIME.AWK
BEGIN {
start = 1 stop = 500 for (i=start; i<=stop; i++) { if (is_prime(i) && is_prime(revstr(i,length(i)))) { printf("%3d%1s",i,++count%10?"":"\n") } } printf("\nReversible primes %d-%d: %d\n",start,stop,count) exit(0)
} function is_prime(x, i) {
if (x <= 1) { return(0) } for (i=2; i<=int(sqrt(x)); i++) { if (x % i == 0) { return(0) } } return(1)
} function revstr(str,start) {
if (start == 0) { return("") } return( substr(str,start,1) revstr(str,start-1) )
} </lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 Reversible primes 1-500: 34
BASIC
<lang basic>10 DEFINT A-Z: MP=999: MX=500 15 MP=10^FIX(LOG(MX)/LOG(10)+1) 20 DIM C(MP): C(0)=-1: C(1)=-1 30 FOR P=2 TO SQR(MP) 40 FOR C=P+P TO MP STEP P: C(C)=-1: NEXT 50 NEXT 60 FOR N=1 TO MX: IF C(N) THEN 100 70 R=0: V=N 80 IF V>0 THEN R=10*R+V MOD 10: V=V\10: GOTO 80 90 IF NOT C(R) THEN PRINT N, 100 NEXT</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
BCPL
<lang bcpl>get "libhdr"
let sieve(prime, n) be $( 0!prime := false
1!prime := false for i = 2 to n do i!prime := true for p = 2 to n/2 if p!prime $( let c = p*2 while c <= n $( c!prime := false c := c+p $) $)
$)
let reverse(n) = valof $( let r=0
while n>0 $( r := 10*r + n rem 10 n := n/10 $) resultis r
$)
let start() be $( let prime = vec 999
sieve(prime, 999) for i = 2 to 500 if i!prime & reverse(i)!prime do writef("%N ",i) wrch('*N')
$)</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
C
<lang c>#include <stdbool.h>
- include <stdio.h>
bool is_prime(unsigned int n) {
if (n < 2) return false; if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; for (unsigned int p = 5; p * p <= n; p += 4) { if (n % p == 0) return false; p += 2; if (n % p == 0) return false; } return true;
}
unsigned int reverse(unsigned int n) {
unsigned int rev = 0; for (; n > 0; n /= 10) rev = rev * 10 + n % 10; return rev;
}
int main() {
unsigned int count = 0; for (unsigned int n = 1; n < 500; ++n) { if (is_prime(n) && is_prime(reverse(n))) printf("%3u%c", n, ++count % 10 == 0 ? '\n' : ' '); } printf("\nCount = %u\n", count); return 0;
}</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 Count = 34
CLU
<lang clu>sieve = proc (max: int) returns (array[bool])
prime: array[bool] := array[bool]$fill(0,max+1,true) prime[0] := false prime[1] := false for p: int in int$from_to(2,max/2) do if ~prime[p] then continue end for c: int in int$from_to_by(p*p,max,p) do prime[c] := false end end return(prime)
end sieve
reverse = proc (n: int) returns (int)
r: int := 0 while n>0 do r := 10*r + n//10 n := n/10 end return(r)
end reverse
start_up = proc ()
po: stream := stream$primary_output() prime: array[bool] := sieve(999) for i: int in int$from_to(2, 500) do if prime[i] cand prime[reverse(i)] then stream$puts(po, int$unparse(i) || " ") end end
end start_up</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Cowgol
<lang cowgol>include "cowgol.coh";
const PRIME_LIMIT := 999; const LIMIT := 500;
var prime: uint8[PRIME_LIMIT + 1]; typedef P is @indexof prime; sub sieve() is
prime[0] := 0; prime[1] := 0; MemSet(&prime[2], 0xFF, @bytesof prime-2); var p: P := 2; while p*p <= PRIME_LIMIT loop if prime[p] != 0 then var c := p*p; while c <= PRIME_LIMIT loop prime[c] := 0; c := c + p; end loop; end if; p := p + 1; end loop;
end sub;
sub reverse(n: P): (r: P) is
r := 0; while n>0 loop r := 10*r + n%10; n := n/10; end loop;
end sub;
sieve(); var n: P := 1; while n <= LIMIT loop
if prime[n] != 0 and prime[reverse(n)] != 0 then print_i32(n as uint32); print_char(' '); end if; n := n + 1;
end loop; print_nl();</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Delphi
<lang Delphi> program Find_prime_n_for_that_reversed_n_is_also_prime;
{$APPTYPE CONSOLE}
uses
System.SysUtils, PrimTrial;
function Reverse(s: string): string; var
i: Integer;
begin
Result := ; if Length(s) < 2 then exit(s); for i := Length(s) downto 1 do Result := Result + s[i];
end;
begin
writeln('working...'#10); var row := 0; var count := 0; var limit := 500;
for var n := 1 to limit - 1 do begin if not isPrime(n) then Continue;
var val := n.ToString; var valr := reverse(val); var nr := valr.ToInteger;
if not isPrime(nr) then Continue;
write(n: 4);
inc(row); inc(count); if row mod 10 = 0 then writeln; end; writeln(#10#10, 'found ', count, ' primes'); Writeln('done...'); readln;
end.</lang>
- Output:
working... 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 found 34 primes done...
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // Reversible Primes. Nigel Galloway: March 22nd., 2021 let emirp2=let rec fN g=function |0->g |n->fN(g*10+n%10)(n/10) in primes32()|>Seq.filter(fN 0>>isPrime) emirp2|>Seq.takeWhile((>)500)|>Seq.iter(printf "%d "); printfn "" </lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Factor
<lang factor>USING: formatting grouping io kernel math math.primes sequences ;
- reverse-digits ( 123 -- 321 )
0 swap [ 10 /mod rot 10 * + swap ] until-zero ;
499 primes-upto [ reverse-digits prime? ] filter dup length "Found %d reverse primes < 500.\n\n" printf 10 group [ [ "%4d" printf ] each nl ] each nl</lang>
- Output:
Found 34 reverse primes < 500. 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Forth
<lang forth>: prime? ( n -- ? ) here + c@ 0= ;
- not-prime! ( n -- ) here + 1 swap c! ;
- prime-sieve ( n -- )
here over erase 0 not-prime! 1 not-prime! 2 begin 2dup dup * > while dup prime? if 2dup dup * do i not-prime! dup +loop then 1+ repeat 2drop ;
- reverse ( n -- n )
0 swap begin dup 0 > while 10 /mod swap rot 10 * + swap repeat drop ;
- main
1000 prime-sieve 0 500 1 do i prime? if i reverse prime? if 1 + i 3 .r dup 10 mod 0= if cr else space then then then loop cr ." Count: " . cr ;
main bye</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 Count: 34
FreeBASIC
Use one of the primality testing algorithms as an include as I can't be bothered putting these in all the time. <lang freebasic>#include "isprime.bas"
function isbackprime( byval n as integer ) as boolean
if not isprime(n) then return false dim as integer m = 0 while n m *= 10 m += n mod 10 n \= 10 wend return isprime(m)
end function
for n as uinteger = 2 to 499
if isbackprime(n) then print n;" ";
next n print</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Frink
<lang frink>select[primes[2,500], {|n| isPrime[parseInt[join["", reverse[integerDigits[n]]]]]}]</lang>
- Output:
[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, 149, 151, 157, 167, 179, 181, 191, 199, 311, 313, 337, 347, 353, 359, 373, 383, 389]
Go
<lang go>package main
import "fmt"
func sieve(limit int) []bool {
limit++ // True denotes composite, false denotes prime. c := make([]bool, limit) // all false by default c[0] = true c[1] = true for i := 4; i < limit; i += 2 { c[i] = true } p := 3 // Start from 3. for { p2 := p * p if p2 >= limit { break } for i := p2; i < limit; i += 2 * p { c[i] = true } for { p += 2 if !c[p] { break } } } return c
}
func reversed(n int) int {
rev := 0 for n > 0 { rev = rev*10 + n%10 n /= 10 } return rev
}
func main() {
c := sieve(999) reversedPrimes := []int{2} for i := 3; i < 500; i += 2 { if !c[i] && !c[reversed(i)] { reversedPrimes = append(reversedPrimes, i) } } fmt.Println("Primes under 500 which are also primes when the digits are reversed:") for i, p := range reversedPrimes { fmt.Printf("%5d", p) if (i+1) % 10 == 0 { fmt.Println() } } fmt.Printf("\n\n%d such primes found.\n", len(reversedPrimes))
}</lang>
- Output:
Primes under 500 which are also primes when the digits are reversed: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 34 such primes found.
Haskell
<lang haskell>import Data.List (intercalate, transpose) import Data.List.Split (chunksOf) import Data.Numbers.Primes (isPrime, primes) import Text.Printf (printf)
PREDICATE -----------------------
p :: Int -> Bool p n = isPrime (read (reverse $ show n) :: Int)
TEST -------------------------
main :: IO () main =
mapM_ putStrLn [ "Reversible primes below 500:", (table " " . chunksOf 10 . fmap show) $ takeWhile (< 500) (filter p primes) ]
FORMATTING ----------------------
table :: String -> String -> String table gap rows =
let widths = maximum . fmap length <$> transpose rows in unlines $ fmap ( intercalate gap . zipWith ( printf . flip intercalate ["%", "s"] . show ) widths ) rows</lang>
- Output:
Reversible primes below 500: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
jq
Works with gojq, the Go implementation of jq
Using the definition of is_prime at Erdős-primes#jq: <lang jq># Generate a stream of reversible primes.
- If . is null the stream is unbounded;
- otherwise only integers less than . are considered.
def reversible_primes:
def r: tostring|explode|reverse|implode|tonumber; (if . == null then infinite else . end) as $n | 2, (range(3; $n; 2) | select(is_prime and (r|is_prime)));
"Primes under 500 which are also primes when the digits are reversed:",
(500 | reversible_primes)</lang>
- Output:
Primes under 500 which are also primes when the digits are reversed: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Julia
<lang julia>using Primes
let
pmask, pcount = primesmask(1, 994), 0 isreversibleprime(n) = pmask[n] && pmask[evalpoly(10, reverse(digits(n)))]
println("Reversible primes between 0 and 500:") for n in 1:499 if isreversibleprime(n) pcount += 1 print(rpad(n, 4), pcount % 17 == 0 ? "\n" : "") end end println("Total found: $pcount")
end
</lang>
- Output:
Reversible primes between 0 and 500: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 Total found: 34
Mathematica /Wolfram Language
<lang Mathematica>Select[Range[499], PrimeQ[#] \[And] PrimeQ[IntegerReverse[#]] &]</lang>
- Output:
{2,3,5,7,11,13,17,31,37,71,73,79,97,101,107,113,131,149,151,157,167,179,181,191,199,311,313,337,347,353,359,373,383,389}
MAD
<lang MAD> NORMAL MODE IS INTEGER
BOOLEAN PRIME DIMENSION PRIME(1000) VECTOR VALUES FMT = $I3*$ PRIME(0)=0B PRIME(1)=0B THROUGH INIT, FOR P=2, 1, P.GE.1000
INIT PRIME(P)=1B
THROUGH SIEVE, FOR P=2, 1, P.GE.32 THROUGH SIEVE, FOR C=P*P, P, C.GE.1000
SIEVE PRIME(C)=0B
THROUGH TEST, FOR N=2, 1, N.GE.500 WHENEVER .NOT. PRIME(N), TRANSFER TO TEST NN=N R=0
RVRSE WHENEVER NN.G.0
NXT=NN/10 R=R*10+NN-NXT*10 NN=NXT TRANSFER TO RVRSE END OF CONDITIONAL WHENEVER .NOT. PRIME(R), TRANSFER TO TEST PRINT FORMAT FMT,N
TEST CONTINUE
END OF PROGRAM</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Modula-2
<lang modula2>MODULE ReversePrime; FROM InOut IMPORT WriteCard, WriteLn;
CONST
Primes = 1000; Max = 500;
VAR prime: ARRAY [1..Primes] OF BOOLEAN;
n, col: CARDINAL;
PROCEDURE reverse(n: CARDINAL): CARDINAL; VAR r: CARDINAL; BEGIN
r := 0; WHILE n > 0 DO r := r*10 + n MOD 10; n := n DIV 10; END; RETURN r;
END reverse;
PROCEDURE Sieve; VAR i, j: CARDINAL; BEGIN
prime[1] := FALSE; FOR i := 2 TO Primes DO prime[i] := TRUE; END; FOR i := 2 TO Primes DIV 2 DO j := i*2; WHILE j <= Primes DO prime[j] := FALSE; j := j + i; END; END;
END Sieve;
BEGIN
Sieve(); col := 0; FOR n := 2 TO Max DO IF prime[n] AND prime[reverse(n)] THEN WriteCard(n,5); col := col + 1; IF col MOD 8 = 0 THEN WriteLn(); END; END; END; WriteLn();
END ReversePrime.</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Nim
<lang Nim>import math, strutils
const
N1 = 499 # Limit for the primes. N2 = 999 # Limit for the reverses of primes.
- Sieve of Erathosthenes.
var composite: array[2..N2, bool] # Default is false. for p in 2..sqrt(N2.toFloat).int:
if not composite[p]: for k in countup(p * p, N2, p): composite[k] = true
template isPrime(n: int): bool = not composite[n]
func reversed(n: int): int =
var n = n while n != 0: result = 10 * result + n mod 10 n = n div 10
var result: seq[int] for n in 2..N1:
if n.isPrime and reversed(n).isPrime: result.add n
for i, n in result:
stdout.write ($n).align(3) stdout.write if (i + 1) mod 10 == 0: '\n' else: ' '
echo()</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Perl
<lang perl>use strict; use warnings; use List::Util 'max'; use ntheory 'is_prime';
sub pp {
my $format = ('%' . (my $cw = 1+length max @_) . 'd') x @_; my $width = ".{@{[$cw * int 60/$cw]}}"; (sprintf($format, @_)) =~ s/($width)/$1\n/gr;
}
my($limit, @rp) = 500; is_prime($_) and is_prime(reverse $_) and push @rp, $_ for 1..$limit; print @rp . " reversible primes < $limit:\n" . pp(@rp);</lang>
- Output:
34 reversible primes < 500: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Phix
function rp(integer p) return is_prime(to_integer(reverse(sprint(p)))) end function procedure test(sequence args) {integer n, string fmt} = args sequence res = apply(true,sprintf,{{"%3d"},filter(get_primes_le(n),rp)}) string r = sprintf(fmt,{join_by(res,1,ceil(length(res)/2)," ")}) printf(1,"%,d reverse primes < %,d found%s\n",{length(res),n,r}) end procedure papply({{500,":\n%s"},{1000,":\n%s"},{10000,"."},{10_000_000,"."}},test)
- Output:
34 reverse primes < 500 found: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 56 reverse primes < 1,000 found: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 701 709 727 733 739 743 751 757 761 769 787 797 907 919 929 937 941 953 967 971 983 991 260 reverse primes < 10,000 found. 82,439 reverse primes < 10,000,000 found.
Python
<lang python>#!/usr/bin/python
def isPrime(n):
for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True
def isBackPrime(n):
if not isPrime(n): return False m = 0 while n: m *= 10 m += n % 10 n //= 10 return isPrime(m)
if __name__ == '__main__':
for n in range(2, 499): if isBackPrime(n): print(n, end=' ');</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
PILOT
<lang pilot>C :n=1
- number
C :p=n U :*prime J (pr=0):*next U :*rev C :p=r U :*prime T (pr):#n
- next
C :n=n+1 J (n<500):*number E :
- rev
C :r=0
- digit
C :z=p/10
:r=r*10+(p-z*10) :p=z
J (z):*digit E :
- prime
C :pr=0 E (p=1): C :pr=1 E (p<4): C :pr=0 E (p=2*(p/2)): C :i=3
- div
E (p=i*(p/i)): C :i=i+2 J (i<p/2):*div C :pr=1 E :</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
PL/I
<lang pli>reversePrimes: procedure options(main);
declare prime(1:999) bit; sieve: procedure; declare (i,j,hi) fixed; hi = hbound(prime,1); prime(1) = '0'b; do i=2 to hi; prime(i) = '1'b; end; do i=2 to sqrt(hi); do j=i*i to hi by i; prime(j) = '0'b; end; end; end sieve; reverse: procedure(nn) returns(fixed); declare (n, nn, r) fixed; r=0; do n=nn repeat(n/10) while (n>0); r = 10*r + mod(n,10); end; return(r); end reverse; declare (n, found) fixed; call sieve; found = 0; do n=1 to 499; if prime(n) & prime(reverse(n)) then do; put edit(n) (F(4)); found = found + 1; if mod(found,20) = 0 then put skip; end; end; put skip list('Reverse primes found:',found);
end reversePrimes;</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 Reverse primes found: 34
Quackery
eratosthenes
and isprime
are defined at Sieve of Eratosthenes#Quackery.
<lang Quackery> 1000 eratosthenes
[ number$ reverse $->n drop ] is revnum ( n --> n )
[ dup isprime iff [ revnum isprime ] else [ drop false ] ] is isrevprime ( n --> b )
[] [] 500 times [ i^ isrevprime if [ i^ join ] ] witheach [ number$ nested join ] 60 wrap$</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
Raku
<lang perl6>unit sub MAIN ($limit = 500); say "{+$_} reversible primes < $limit:\n{$_».fmt("%" ~ $limit.chars ~ "d").batch(10).join("\n")}",
with ^$limit .grep: { .is-prime and .flip.is-prime }</lang>
- Output:
34 reversible primes < 500: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389
REXX
<lang rexx>/*REXX program counts/displays the number of reversed primes under a specified number N.*/ parse arg n cols . /*get optional number of primes to find*/ if n== | n=="," then n= 500 /*Not specified? Then assume default.*/ if cols== | cols=="," then cols= 10 /* " " " " " */ call genP copies(9, length(n) ) /*generate all primes under N. */ w= 10 /*width of a number in any column. */ if cols>0 then say ' index │'center(" reversed primes that are < " n, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') Rprimes= 0; idx= 1 /*initialize # of additive primes & idx*/ $= /*a list of additive primes (so far). */
do j=2 until j>=n; if \!.j then iterate /*Is J not a prime? No, then skip it.*/ _= reverse(j); if \!._ then iterate /*is sum of J's digs a prime? No, skip.*/ Rprimes= Rprimes + 1 /*bump the count of additive primes. */ if cols<1 then iterate /*Build the list (to be shown later)? */ $= $ right( commas(j), w) /*add the additive prime to the $ list.*/ if Rprimes//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'found ' commas(Rprimes) " reversed primes < " commas(n) exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: parse arg h; @.=.; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; #= 7
w= length(h); !.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1 do j=@.7+2 by 2 while j<h /*continue on with the next odd prime. */ parse var j -1 _ /*obtain the last digit of the J var.*/ if _ ==5 then iterate /*is this integer a multiple of five? */ if j // 3 ==0 then iterate /* " " " " " " three? */ /* [↓] divide by the primes. ___ */ do k=4 to # while k*k<=j /*divide J by other primes ≤ √ J */ if j//@.k == 0 then iterate j /*÷ by prev. prime? ¬prime ___ */ end /*k*/ /* [↑] only divide up to √ J */ #= # + 1; @.#= j; !.j= 1 /*bump prime count; assign prime & flag*/ end /*j*/ return</lang>
- output when using the default inputs:
index │ reversed primes that are < 500 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 2 3 5 7 11 13 17 31 37 71 11 │ 73 79 97 101 107 113 131 149 151 157 21 │ 167 179 181 191 199 311 313 337 347 353 31 │ 359 373 383 389 found 34 reversed primes < 500
- output when using the inputs: 10000 0
found 260 reversed primes < 10,000
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl
row = 0 num = 0 limit = 500
for n = 1 to limit
strm = "" strn = string(n) for m = len(strn) to 1 step -1 strm = strm + strn[m] next strnum = number(strm) if isprime(n) and isprime(strnum) num = num + 1 row = row + 1 see "" + n + " " if row%10 = 0 see nl ok ok
next
see nl + "found " + num + " primes" + nl see "done..." + nl </lang>
- Output:
working... 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 found 34 primes done...
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func boolean: isPrime (in integer: number) is func
result var boolean: prime is FALSE; local var integer: upTo is 0; var integer: testNum is 3; begin if number = 2 then prime := TRUE; elsif odd(number) and number > 2 then upTo := sqrt(number); while number rem testNum <> 0 and testNum <= upTo do testNum +:= 2; end while; prime := testNum > upTo; end if; end func;
const func integer: revDigits (in var integer: number) is func
result var integer: revNum is 0; begin while number > 0 do revNum *:= 10; revNum +:= number rem 10; number := number div 10; end while; end func;
const func boolean: isRevPrime (in integer: number) is
return isPrime(number) and isPrime(revDigits(number));
const proc: main is func
local var integer: number is 0; var integer: count is 0; begin for number range 1 to 499 do if isRevPrime(number) then write(number <& " "); incr(count); end if; end for; writeln; writeln("Found " <& count <& " reverse primes < 500."); end func;</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 Found 34 reverse primes < 500.
Sidef
<lang ruby>say primes(500).grep { .reverse.is_prime }</lang>
- Output:
[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 101, 107, 113, 131, 149, 151, 157, 167, 179, 181, 191, 199, 311, 313, 337, 347, 353, 359, 373, 383, 389]
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt import "/seq" for Lst
var reversed = Fn.new { |n|
var rev = 0 while (n > 0) { rev = rev * 10 + n % 10 n = (n/10).floor } return rev
}
var primes = Int.primeSieve(499) var reversedPrimes = [] for (p in primes) {
if (Int.isPrime(reversed.call(p))) reversedPrimes.add(p)
} System.print("Primes under 500 which are also primes when the digits are reversed:") for (chunk in Lst.chunks(reversedPrimes, 17)) Fmt.print("$3d", chunk) System.print("\n%(reversedPrimes.count) such primes found.")</lang>
- Output:
Primes under 500 which are also primes when the digits are reversed: 2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 34 such primes found.
XPL0
<lang XPL0>func IsPrime(N); \Return 'true' if N is a prime number int N, I; [if N <= 1 then return false; for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true; ];
func Reverse(N); \Return the reverse of the digits in N int N, M; [M:= 0; while N do
[N:= N/10; M:= M*10 + rem(0); ];
return M; ];
int Count, N; [Count:= 0; for N:= 1 to 499 do
[if IsPrime(N) & IsPrime(Reverse(N)) then [IntOut(0, N); Count:= Count+1; if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\); ] ];
CrLf(0); IntOut(0, Count); Text(0, " reversible primes found."); ]</lang>
- Output:
2 3 5 7 11 13 17 31 37 71 73 79 97 101 107 113 131 149 151 157 167 179 181 191 199 311 313 337 347 353 359 373 383 389 34 reversible primes found.
- Draft Programming Tasks
- Prime Numbers
- 11l
- Action!
- Action! Sieve of Eratosthenes
- Ada
- ALGOL W
- AWK
- BASIC
- BCPL
- C
- CLU
- Cowgol
- Delphi
- System.SysUtils
- PrimTrial
- F Sharp
- Factor
- Forth
- FreeBASIC
- Frink
- Go
- Haskell
- Jq
- Julia
- Mathematica
- Wolfram Language
- MAD
- Modula-2
- Nim
- Perl
- Ntheory
- Phix
- Python
- PILOT
- PL/I
- Quackery
- Raku
- REXX
- Ring
- Seed7
- Sidef
- Wren
- Wren-math
- Wren-fmt
- Wren-seq
- XPL0