Emirp primes: Difference between revisions

{{trans|Nim}}

 

V result = 0

L

I ++count == 10000

print(‘The 10000th emirp: ’n)

 

{{out}}

he solution uses the package Miller_Rabin from the [[Miller-Rabin primality test]].

 

 

procedure Emirp_Gen is

end loop;

Ada.Text_IO.Put_Line(Num'Image(Current));

 

{{out}}

Allows the user to specify the from and to range values or ordinals on the command line. The sieve size can also be specified. As suggested by the Fortran sample, from = to is treated as a special case for labeling the output.

{{libheader|ALGOL 68-primes}}

INT emirp from := 1; # lowest emirp required #

INT emirp to := 10; # highest emirp required #

OD

FI;

{{out}}

a68g emirpPrimes.a68 - FROM 1 TO 20

=={{header|Arturo}}==

 

result: new []

loop range .step: 2 11 upto 'x [

print ""

print "The 10000th emirp:"

 

{{out}}

 

=={{header|AutoHotkey}}==

p := 1

Loop, 20 {

r := A_LoopField r

return r

{{Output}}

<pre>First twenty emirps: 13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

 

cat emirp.awk

function is_prime(n, p)

{

printf("\n")

}

{{Output}}

<pre>

948349

</pre>

 

=={{header|C}}==

Note the unusual commandline argument parsing to sastisfy the "invoke three times" magic requirement.

 

typedef unsigned uint;

putchar('\n');

return 0;

{{out}}

<pre>

</pre>

 

{{works with|C sharp|7}}

using System;

using System.Linq;

return reverse;

}

{{out}}

<pre>

 

=={{header|C++}}==

#include <iostream>

#include <algorithm>

 

return 0 ;

{{out}}

<pre>13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

===Using biginteger's isProbablePrime()===

The isProbablePrime() method performs a Miller-Rabin primality test to within a given certainty.

(let [a (biginteger v)

b (biginteger (clojure.string/reverse (str v)))]

(println "10,000: " (nth (filter emirp? (iterate inc 0)) 9999))

 

{{out}}

<pre>first20: 13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

 

It uses a primitive prime function found in http://www.rosettacode.org/wiki/Primality_by_trial_division, not optimized at all.

"Is N prime?"

(and (> n 1)

(format t "~%Emirps between 7700 and 8000: ") (emirp :start 7700 :end 8000 :print-all t)

(format t "~%The 10,000'th emirp: ") (emirp :count 10000 :print-all nil) )

 

{{out}}

 

=={{header|D}}==

bool isPrime(in uint n) pure nothrow @nogc {

if (n == 2 || n == 3)

iota(7_700, 8_001).filter!isEmirp);

writeln("10000th: ", uints.filter!isEmirp.drop(9_999).front);

{{out}}

<pre>First 20:

 

===Sieve-Based Version===

 

/// Not extendible Sieve of Eratosthenes.

iota(7_700, 8_001).filter!isEmirp);

writeln("10000th: ", uints.filter!isEmirp.drop(9_999).front);

The output is the same. With ldc2 compiler the run-time is about 0.06 seconds.

=={{header|Delphi}}==

See [https://rosettacode.org/wiki/Emirp_primes#Pascal Pascal].

 

=={{header|Elixir}}==

defp prime?(2), do: true

defp prime?(n) when n<2 or rem(n,2)==0, do: false

end

 

 

{{out}}

===The function===

This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]

// Generate emirps. Nigel Galloway: November 19th., 2017

let emirp =

let fG n g = n<>g && isPrime g

primes32() |> Seq.filter (fun n -> fG n (fN n 0))

 

===The Task===

emirps |> (Seq.take 20) |> Seq.iter (printf "%d ")

{{out}}

<pre>

13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

</pre>

emirps |> Seq.skipWhile (fun n->n<7700) |> Seq.takeWhile (fun n->n<=8000) |> Seq.iter (printf "%d ")

{{out}}

<pre>

7717 7757 7817 7841 7867 7879 7901 7927 7949 7951 7963

</pre>

printfn "%d" (Seq.item 9999 emirps)

{{out}}

<pre>

948349

</pre>

// count # of emirps with n = 2 to 7 digits. Nigel Galloway: August 8th., 2018

let n=emirp |> Seq.takeWhile(fun n->n<10000000) |> Seq.countBy(fun n->match n with |n when n>999999->7

|_ ->2)

for n,g in n do printfn "%d -> %d" n g

{{out}}

<pre>

 

=={{header|Factor}}==

math.primes sequences ;

FROM: prettyprint => . pprint ;

part1 nl part2 nl part3 ;

{{out}}

<pre>

=={{header|Forth}}==

Keeps a pair of numbers on the stack to represent a generator. This generator approach means that all tasks start from the first Emirp (13), even task 2.

#! /usr/bin/gforth-fast

 

task1 task2 task3

cr bye

{{Out}}

<pre>

For factoring numbers up to the 32-bit two's complement integer limit, the table need not be large, and it can easily enough be stored as a collection of sixteen and thirty-two bit numbers to save some space. Accessing an array PRIME(i) can be made a function GETPRIME(i) without a change in syntax (as needed in pascal: Prime[i] for an array, GetPrime(i) for a function), at least for reading. So, instead of 4792x4 = 19168 bytes, 12144 are needed, to set against the additional code complexity. These days, this is a difference of small importance. Actually, a further value is needed to hold Prime(4793) = 46349. Function ISPRIME does not determine its stepping point via the near universal usage of SQRT(n). If calculated in double precision this will give acceptable results for a 32-bit integer, but I have been burnt by an ad-hoc calculation nDgits = LOG10(x) + 1 failing for x = 10 because Log10(10) = 0·9999etc. which may well round to one, but truncates to zero. So, a SQRT-free demonstration, needed if the MOD function were unavailable. Actually, if P(i) is the last factor to be checked, this suffices up to the square of P(i + 1), not P(i). But this bound is only useful when successive numbers are being tested; for an individual factorisation it is too messy.

 

INTEGER MSG !I/O unit number to share about.

INTEGER PF16LIMIT,PF32LIMIT,NP !Know that P(3512) = 32749, the last within two's complement 16-bit integers.

CALL EMIRP(10,10000,10000, 1,1000000) !Of three separate invocations.

 

Output:

<pre>

 

=={{header|FreeBASIC}}==

 

Function isPrime(n As UInteger) As Boolean

Print

Print "Press any key to quit"

 

{{out}}

 

=={{header|Frink}}==

isEmirp[x] :=

{

println["Range: " + emirps[7700, 8000]]

println["10000th: " + last[first[emirps[], 10000]]]

{{out}}

<pre>

10000th: 948349

</pre>

 

=={{header|Go}}==

 

As a side note, by using the same API as the prime number generator this also demonstrates how Go interfaces can be used (and note it doesn't require the existing code/package to know anything about the interface being defined).

 

import (

fmt.Println()

}

{{out}}

<pre>

=={{header|Groovy}}==

{{trans|Java}}

 

//trivial prime algorithm, sub in whatever algorithm you want

println(--x)

}

{{out}}

<pre>First 20 emirps:

{{Works with|primes|0.2.1.0}}

 

 

import Data.HashSet (HashSet, fromList, member)

"slice" -> print $ emirpSlice lo hi

"values" -> print $ emirpValues lo hi

 

{{out}}

===List-based===

Using list-based incremental sieve from [[Sieve_of_Eratosthenes#With_Wheel|here]] and trial division from [[Primality_by_trial_division#Haskell|here]],

 

λ> take 20 . filter emirp $ primesW

 

λ> (!! (10000-1)) . filter emirp $ primesW

 

=={{header|J}}==

 

 

In other words: select numbers from the argument list whose decimal reverse is both different and prime and return those decimal reversed values as numbers. (For simplicity, we require that our argument be a list of prime numbers.)

 

13 17 31 37 71 73 79 97 113 311 701 733 743 751 761 941 953 971 983 991

 

NB. alternative approach (first emirp value would be at index 0):

9999 { /:~ emirp p:i.1e5

 

=={{header|Java}}==

This implementation uses a slight optimization discussed in the talk page. It will not actually check the primality (forwards or backwards) for a number that starts or ends with the digits 2, 4, 5, 6, or 8 since no primes greater than 7 end with those digits.

//trivial prime algorithm, sub in whatever algorithm you want

System.out.println(--x);

}

{{out}}

<pre>First 20 emirps:

=={{header|JavaScript}}==

Script source

if (!(n % 2) || !(n % 3)) return 0;

 

}

}

 

Solution page

<html>

<head>

<div id="content"></div>

</body>

{{out}}

<pre>13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

 

'''Infrastructure: prime numbers'''

if . == 2 then true

else

| until( relatively_prime ; .[0] += 2) as $nextp

| ( $previous + [$nextp[0]] );

 

'''Emirps'''

. as $n

| tostring | explode | reverse | implode | tonumber | (. != $n) and is_prime ;

else if ($p | is_emirp) then [.[0] + 1, $p] else .[1] = null end

end;

 

'''The tasks'''

 

(0) The three separate subtasks can be accomplished in one step as follows:

 

The output of the above is shown below.

 

(1) First twenty:

 

(2) Selection by value

| primes

| if (7700 <= .) and (. <= 8000) and is_emirp then .

elif . > 8000 then break $top

else empty

 

(3) 10,000th

 

{{out}}

[1,13]

[2,17]

[189,7951]

[190,7963]

 

=={{header|Julia}}==

 

function collapse(n::Array{<:Integer})

println("Between 7700 and 8000:\n", filter(x -> 7700 ≤ x ≤ 8000, emirps))

println("10000th:\n", emirps[10000])

<pre>

First 20:

=={{header|Kotlin}}==

{{trans|FreeBASIC}}

 

fun isPrime(n: Int) : Boolean {

while(true)

print(i)

 

{{out}}

The 10,000th Emirp prime is : 948349

</pre>

 

=={{header|Lua}}==

function isPrime (n)

if n < 2 then return false end

print("Wrong number of arguments")

end

Command prompt session:

<pre>

 

=={{header|Maple}}==

local eprime;

eprime := parse(StringTools:-Reverse(convert(n,string)));

EmirpPrime~([seq(7700..8000)]);

EmirpsList(10000)[-1];

{{out}}

<pre>[13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, 311, 337, 347, 359, 389]

=={{header|Mathematica}}/{{header|Wolfram Language}}==

First a simple helper function

A function to test whether n is an emirp prime

Note, this test function assumes n is prime. Adding a check to verify n is prime will have

an impact on execution time for finding the mth emirp prime particularly when m is large.

 

Finally, a function which returns the first emirp prime larger than the supplied argument

 

With these the first 20 emirp primes are computed as:

{{out}}

<pre>

 

The emirp primes betweewn 7700 and 8000 are:

{{out}}

<pre>

 

The 10,000th emirp prime is:

{{out}}

<pre>

 

=={{header|MATLAB}}==

NN=(1:1:1e6); %Natural numbers between 1 and t

pns=NN(isprime(NN)); %prime numbers

a=pns(isprime(p)); b=p(isprime(p)); c=a-b;

emirps=NN(a(c~=0));

{{out}}

<pre>the first twenty emirps are: emirps(1:20)

 

=={{header|Modula-2}}==

FROM Conversions IMPORT StrToLong;

FROM FormatString IMPORT FormatString;

 

ReadChar

 

=={{header|Nim}}==

===Using a simple test of primality===

This is not the most efficient way to solve the tasks, but it doesn’t set a limit ''a priori''. We have done some optimizations to speed up the primality test. Using a cache didn’t improve the times. The program runs in about 100 ms.

 

# Increments to find the next divisor when testing primality.

if count == 10000:

echo n

 

{{out}}

The sieve is a simple one, with no optimization to reduce its size. As it is a non-extensible sieve, there is a limit. So, in task 3, we check if the sieve size must be increased. The program runs in about 6 ms.

 

 

const N = 1_000_000

break

if count < 10000:

 

{{out}}

The 10000th emirp: 948349</pre>

 

 

Using isPrime function of Primality by trial division task :

 

n isPrime ifFalse: [ false return ]

n asString reverse asInteger dup n == ifTrue: [ drop false ] else: [ isPrime ] ;

dup isEmirp ifTrue: [ dup l add ] 1 +

]

 

{{out}}

 

=={{header|PARI/GP}}==

emirp(n)=my(r=rev(n)); isprime(r) && isprime(n) && n!=r

select(emirp, primes(100))[1..20]

select(emirp, primes([7700,8000]))

{{out}}

<pre>%1 = [13, 17, 31, 37, 71, 73, 79, 97, 107, 113, 149, 157, 167, 179, 199, 311, 337, 347, 359, 389]

using trial division unit , but jumping over number ranges, where the reversed numbers can't be a prime.

Compiles with Delphi and Free Pascal.

//palindrome prime 13 <-> 31

{$IFDEF FPC}

OutPutHelp;

end;

;output:

<pre>

=={{header|Perl}}==

{{libheader|ntheory}}

use ntheory qw(forprimes is_prime);

 

forprimes { print " $_" if is_prime(reverse $_) && $_ ne reverse($_) } 7700,8000;

print "\n";

{{out}}

<pre>First 20: 13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389

=={{header|Phix}}==

Does not assume anywhere that some pre-guessed value will be enough.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">emirps</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>

<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cl</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>

<span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1-20"</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">usage</span><span style="color: #0000FF;">()</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

{{Out}}

<pre>

=={{header|PHP}}==

 

 

function is_prime($n) {

'First twenty emirps :', PHP_EOL, $first20, PHP_EOL,

'Emirps between 7,700 and 8,000 :', PHP_EOL, $between, PHP_EOL,

 

{{out}}

 

=={{header|PicoLisp}}==

(and

(bit? 1 N)

(println (take1 20))

(println (take2))

{{out}}

<pre>(13 17 31 37 71 73 79 97 107 113 149 157 167 179 199 311 337 347 359 389)

 

=={{header|PL/I}}==

pt1: Proc(run) Options(main);

/*********************************************************************

End;

 

 

{{out}}

 

There is no explicit hard-coded ceiling added to the code for the prime generator, which is the reason given for the need to invoke a program three times in the task description.

from prime_decomposition import primes, is_prime

from heapq import *

if pr >= 7700: print(pr, end=', ')

print(']')

 

{{out}}

<code>eratosthenes</code> and <code>isprime</code> are defined at [[Sieve of Eratosthenes#Quackery]].

 

[ [] swap

[ dip 1+ ]

over 10000 = until ]

 

{{out}}

 

=={{header|R}}==

library(gmp)

 

cat("The 10000th emirp: ")

emirp(ignore = 9999, howmany = 1)

{{out}}

<pre>

basic functions, unburdened by accounting or (too many) performance

considerations (please don't mark this as needing attention... I know it falls short of

(require math/number-theory)

 

(let loop ((i 10000) (p 9))

(define p+2 (+ p 2))

 

The second is somewhat larger and seems to be a playground for all sorts of code.

;; ---------------------------------------------------------------------------------------------------

;; There are two distinct requirements here...

(check-equal? (time (task2 emirp-prime?/sieve)) (time (task2)))

(check-equal? (time (task3 emirp-prime?/sieve extend-sieve!)) (time (task3))))

 

{{out}}

For better performance, build the lazy list using module <code>Math::Primesieve</code>, not the built-in, then display results based on parameters passed in. The default is to display an array slice starting and stopping at the given indices. Alternately, ask for all values between two endpoints.

 

 

sub prime-hash (Int $max) {

}

}

{{out}}

Run with passed parameters: 1 20

<br>memoization was added (assisting with the <big>√{{overline|&nbsp;j&nbsp;}}</big>), &nbsp; and some of the trial divisions were hard-coded to minimize

<br>the CPU time a bit.

parse arg x y . /*obtain optional arguments from the CL*/

if x=='' | x=="," then do; x=1; y=20; end /*Not specified? Then use the default.*/

/* [↓] display the emirp list. */

say strip($); say; n=words($); ?=(n\==1) /*display the emirp primes wanted. */

'''output''' &nbsp; when using the following for input: &nbsp; <tt> 1 &nbsp; 20 </tt>

<pre>

 

===version 2===

* 27.03.2014 Walter Pachl

*********************************************************************/

Say l

End

'''output'''<pre>rexx ptz 1

the first 20 emirps:

 

=={{header|Ring}}==

nr = 1

m = 2

next

return true

 

=={{header|Ruby}}==

 

emirp = Enumerator.new do |y|

break

end

 

{{out}}

 

=={{header|Rust}}==

 

extern crate primal;

println!("Emirps-s between 7700 and 8000 : {:?}", vec2);

println!("10.000-th emirp : {}", emirp_10_000);

{{out}}

<pre>

===Using BigInt's isProbablePrime()===

The isProbablePrime() method performs a Miller-Rabin primality test to within a given certainty.

val b = BigInt(v.toLong)

val r = BigInt(v.toString.reverse.toLong)

println( "%32s".format( "Emirps between %d and %d: ".format( b1, b2 )) + {for( i <- b1 to b2 if( isEmirp(i) ) ) yield i}.mkString(",") )

println( "%32s".format( "%,d emirp: ".format( c )) + Iterator.from(2).filter( isEmirp(_) ).drop(c-1).next )

{{out}}

<pre> First 20 emirps: 13,17,31,37,71,73,79,97,107,113,149,157,167,179,199,311,337,347,359,389

Emirps between 7700 and 8000: 7717,7757,7817,7841,7867,7879,7901,7927,7949,7951,7963

10,000 emirp: 948349</pre>

 

=={{header|Sidef}}==

{{trans|Perl}}

for (var p = a.dec.next_prime; p <= b; p.next_prime!) {

callback(p)

forprimes(7700, 8000, {|p| is_emirp(p) && take(p) })

}.join(' '))

{{out}}

<pre>

 

First an emirp checker:

[:p | |e|

(e := p asString reversed asNumber) isPrime

and:[ e ~= p ]

 

an infinite list of primes:

[:n |

LazyCons car:n cdr:[primeGen value:(n nextPrime)]

 

an infinite list of emirps, taking an infinite list of primes as arg:

[:l | |rest el|

rest := l.

[ el := rest car. rest := rest cdr. isEmirp value:el ] whileFalse.

LazyCons car:el cdr:[emirpGen value:rest]

two infinite lists:

generating output:

show:'first 20 emirps: ';

showCR:(listOfEmirps take:20) asArray.

Transcript

show:'10000''th emirp: ';

 

Generates:<pre>

 

LazyCons is easily defined as:

instancevariableNames:'car cdr'.

 

cdr := cdr value.

self changeClassTo:Cons.

 

=={{header|Stata}}==

 

list in 1/20, noobs noh

 

+--------+

| 948349 |

 

Now the definition of ''emirp.ado'':

 

args n

qui clear

st_store(.,1,a)

}

 

=={{header|Swift}}==

 

 

extension BinaryInteger {

print("First 20 emirps: \(Array(lots.prefix(20)))")

print("Emirps between 7700 and 8000: \(rang)")

 

{{out}}

=={{header|Tcl}}==

{{tcllib|math::numtheory}}

 

# Import only to keep line lengths down

if {[emirp? $n] && [incr ne] == 10000} break

}

{{out}}

<pre>

=={{header|VBA}}==

 

 

Private Const MAX As Long = 5000000

On Error GoTo 0

End If

{{out}}

<pre>At this point : Execution time = 13,23047 seconds.

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Module Module1

End Sub

 

{{out}}

<pre>First 20:

=={{header|Wren}}==

{{libheader|Wren-math}}

 

var isEmirp = Fn.new{ |n|

}

}

 

{{out}}

 

The 10,000th emirp is 948349

</pre>

 

=={{header|zkl}}==

Uses the solution from task [[Extensible prime generator#zkl]]. Saves the primes to a list, which gets pretty big.

var ps=Utils.Generator(PS), plist=ps.walk(10).copy();

 

Utils.Generator(PS).filter(fcn(p){if(p>8000)return(Void.Stop); p>7700 and isEmirp(p)});

 

{{out}}

<pre>