Truncatable primes: Difference between revisions

{{task|Prime Numbers}}

 

 

 

 

* [[Find largest left truncatable prime in a given base]]

* [[Sieve of Eratosthenes]]

 

<br><br>

 

=={{header|Ada}}==

with Ada.Text_IO; use Ada.Text_IO;

with Ada.Containers.Ordered_Sets;

end loop;

end Truncatable_Primes;

Sample output:

<pre>

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny].}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

 

PROC is prime = (INT n)BOOL:(

write("Press Enter");

read(newline)

Output:

<pre>

Press Enter

</pre>

 

=={{header|AutoHotkey}}==

MsgBox, % "Largest left-truncatable and right-truncatable primes less than one million:`n"

. "Left:`t" LTP(10 ** 6) "`nRight:`t" RTP(10 ** 6)

return, 1

}

'''Output:'''

<pre>Largest left-truncatable and right-truncatable primes less than one million:

Left: 998443

Right: 739399</pre>

 

=={{header|Bracmat}}==

Primality test: In an attempt to compute the result of taking a (not too big, 2^32 or 2^64, depending on word size) number to a fractional power, Bracmat computes the prime factors of the number and checks whether the powers of prime factors make the fractional power go away. If the number is prime, the output of the computation is the same as the input.

& whl

' ( !i+-2:>0:?i

)

& out$("right:" !i)

Output:

<pre>left: 998443

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

printf("Left: %d; right: %d\n", max_left, max_right);

return 0;

 

Faster way of doing primality test for small numbers (1000000 isn't big), and generating truncatable primes bottom-up:

 

#define MAXN 1000000

 

return 0;

{{out}}

<pre>

 

=={{header|C sharp|C#}}==

{

{

}

 

{

}

 

{

}

 

{

break;

}

}

 

=={{header|Clojure}}==

 

(def prime?

((juxt ffirst (comp second second)) ,)

(map vector ["left truncatable: " "right truncatable: "] ,))

 

=={{header|CoffeeScript}}==

# truncatable numbers, but they lend themselves to slightly

# different optimizations.

console.log "right", max_right_truncatable_number(999999, is_prime)

console.log "left", max_left_truncatable_number(999999, is_prime)

output

> coffee truncatable_prime.coffee

right 739399

left 998443

 

=={{header|Common Lisp}}==

(defun start ()

(format t "Largest right-truncatable ~a~%" (max-right-truncatable))

((zerop (rem n d)) nil)

(t (primep-aux n (+ d 1)))))

{{out}}

<pre>Largest right-truncatable 739399

 

=={{header|D}}==

std.range;

 

writeln("Largest right-truncatable prime in 2 .. ", n, ": ",

iota(n, 1, -1).filter!(isTruncatablePrime!false).front);

{{out}}

<pre>Largest left-truncatable prime in 2 .. 1000000: 998443

Largest right-truncatable prime in 2 .. 1000000: 739399</pre>

 

=={{header|EchoLisp}}==

;; does p include a 0 in its decimal representation ?

(define (nozero? n) (= -1 (string-index (number->string n) "0")))

(define (fact-trunc trunc)

(for ((p (in-range 999999 100000 -1))) #:break (when (trunc p) (writeln p) #t)))

Output:

(fact-trunc left-trunc)

998443

(fact-trunc right-trunc)

739399

 

=={{header|Eiffel}}==

class

APPLICATION

 

end

{{out}}

<pre>

 

=={{header|Elena}}==

 

 

extension mathOp

{

while (f <= r)

while (n != 0)

 

while (tens < n)

while (n != 0)

 

}

 

 

 

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Ruby}}

defp left_truncatable?(n, prime) do

func = fn i when i<=9 -> 0

end

 

 

{{out}}

Largest left-truncatable prime : 998443

Largest right-truncatable prime: 739399

</pre>

 

=={{header|Fortran}}==

{{works with|Fortran|95 and later}}

implicit none

end if

end do

Output

<pre>Largest left truncatable prime below 1000000 is 998443

=={{header|FreeBASIC}}==

===Version 1===

 

Function isPrime(n As Integer) As Boolean

Print

Print "Press any key to quit"

 

{{out}}

===Version 2===

Construct primes using previous found primes.

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>

 

=={{header|Go}}==

 

import "fmt"

}

return false

Output:

<pre>

=={{header|Haskell}}==

Using {{libheader|Primes}} from [http://hackage.haskell.org/packages/hackage.html HackageDB]

import Data.List

import Control.Arrow

let (ltp, rtp) = (head. filter leftT &&& head. filter rightT) primes1e6

putStrLn $ "Left truncatable " ++ show ltp

Output:

Left truncatable 998443

 

Interpretation of the J contribution:

smallPrimes = filter isPrime digits

pow10 = iterate (*10) 1

lefT = liftM2 (.) (+) ((*) . mul10)

 

Output:

739399

 

*Main> maximum $ primesTruncatable lefT !! 5

 

N := 0 < integer(\arglist[1]) | 1000000 # primes to generator 1 to ... (1M or 1st arglist)

D := (0 < integer(\arglist[2]) | 10) / 2 # primes to display (10 or 2nd arglist)

procedure islefttrunc(P,x) #: return integer x if x and all left truncations of x are in P or fails

if *x = 0 | ( (x := integer(x)) & member(P,x) & islefttrunc(P,x[2:0]) ) then return x

 

Sample output:<pre>There are 78498 prime numbers in the range 1 to 1000000

Largest right truncatable prime = 739399</pre>

 

 

Truncatable primes may be constructed by starting with a set of one digit prime numbers and then repeatedly adding a non-zero digit (combine all possibilities of a truncatable prime digit sequence with each digit) and, at each step, selecting the prime numbers which result.

In other words, given:

 

seed=: selPrime digits=: 1+i.9

 

Here, selPrime discards non-prime numbers from a list, so seed is the list 2 3 5 7.

The largest truncatable primes less than a million can be obtained by adding five digits to the prime seeds, then finding the largest value from the result.

 

998443

>./ step&digits^:5 seed NB. right truncatable

 

Note that we are using the same combining function and same basic procedure in both cases. The difference is which side of the number we add arbitrary digits to, for each step.

 

=={{header|Java}}==

 

public class Main {

}

}

Output :

<pre>

Right Truncatable : 739399

</pre>

 

=={{header|Julia}}==

There are several features of Julia that make solving this task easy. Julia has excellent built-in support for prime generation and testing. The built-in mathematical functions <tt>prevpow</tt> and <tt>divrem</tt> are quite handy for implementing <tt>isltruncprime</tt>.

function isltruncprime{T<:Integer}(n::T, base::T=10)

isprime(n) || return false

break

end

 

{{out}}

=={{header|Kotlin}}==

{{trans|FreeBASIC}}

 

fun isPrime(n: Int) : Boolean {

println("Largest left truncatable prime : " + lMax.toString())

println("Largest right truncatable prime : " + rMax.toString())

 

{{out}}

 

=={{header|Lua}}==

 

numbers = {}

 

print( "max_prime_left = ", max_prime_left )

 

And @@ PrimeQ /@ ToExpression /@ StringJoin /@

Rest[Most[NestList[Rest, #, Length[#]] &[Characters[ToString[n]]]]]

RightTruncatablePrimeQ[n_] := Times @@ IntegerDigits[n] > 0 &&

And @@ PrimeQ /@ ToExpression /@ StringJoin /@

Example usage:

<pre>n = PrimePi[1000000]; While[Not[LeftTruncatablePrimeQ[Prime[n]]], n--]; Prime[n]

-> 998443

n = PrimePi[1000000]; While[Not[RightTruncatablePrimeQ[Prime[n]]], n--]; Prime[n]

-> 739399</pre>

=={{header|MATLAB}}==

largestTruncatablePrimes.m:

 

%Helper function for checking if a prime is left of right truncatable

end

end

Solution for n = 1,000,000:

>> largestTruncatablePrimes(1e6)

998443 is the largest left truncatable prime <= 1000000.

739399 is the largest right truncatable prime <= 1000000.

 

=={{header|Nim}}==

 

for i in 2..n:

if i notin multiples:

for j in countup(i*i, n, i.int):

multiples.incl j

var

for x in primes(n):

primelist.add($x)

reverse primelist

for n in primelist:

if alltruncs <= primeset:

result.left = parseInt(n)

break

for n in primelist:

alltruncs.incl n[0..i]

if alltruncs <= primeset:

result.right = parseInt(n)

break

 

 

=={{header|ooRexx}}==

-- find largest left- & right-truncatable primes < 1 million.

-- an initial set of primes (not, at this time, we leave out 2 because

say 'The largest right-truncatable prime is' lastRight '(under one million).'

 

Output:

<pre>

 

=={{header|OpenEdge/Progress}}==

i_i AS INT

):

getHighestTruncatablePrimes( 1000000 )

VIEW-AS ALERT-BOX.

Output:

<pre>---------------------------

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

This version builds the truncatable primes with up to k digits in a straightforward fashion. Run time is about 15 milliseconds, almost all of which is I/O.

my(v=[2,3,5,7],u,t=1,out=0);

for(i=1,n,

out

};

 

=={{header|Perl}}==

Typically with Perl we'll look for a CPAN module to make our life easier. This basically just follows the task rules:

{{libheader|ntheory}}

sub isltrunc {

my $n = shift;

for (reverse @{primes(1e6)}) {

if (isrtrunc($_)) { print "rtrunc: $_\n"; last; }

{{out}}

<pre>ltrunc: 998443

rtrunc: 739399</pre>

We can be a little more Perlish and build up n-digit lists then select the last one:

 

my @lprimes = my @rprimes = (2,3,5,7);

for 2..6;

 

 

Or we can do everything ourselves:

use warnings;

use strict;

}

 

{{out}}

<pre>left 998443, right 739399</pre>

 

 

=={{header|PicoLisp}}==

 

(de truncatablePrime? (N Fun)

(until (truncatablePrime? (dec 'Left) cdr))

(until (truncatablePrime? (dec 'Right) '((L) (cdr (rot L)))))

Output:

<pre>-> (998443 . 739399)</pre>

 

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

tp: procedure options (main);

declare primes(1000000) bit (1);

 

end tp;

<pre>

739399 is right-truncatable

 

=={{header|PowerShell}}==

{

$isprime = @{}

"Largest Right Truncatable Prime: $lastrtprime"

}

 

=={{header|PureBasic}}==

 

Procedure is_Prime(n)

y.s="Largest TruncateRight= "+Str(truncateright)

 

 

 

def primes(n):

return truncateleft, truncateright

 

 

'''Sample Output'''

<pre>(998443, 739399)</pre>

 

=={{header|Racket}}==

 

#lang racket

(require math/number-theory)

998443

739399

=={{header|REXX}}==

Extra code was added to the prime number generator as this is the section of the REXX program that consumes the vast majority of the computation time.

/* [↓] find largest left truncatable P*/

leave /*egress, found left truncatable prime.*/

/* [↓] find largest right truncated P.*/

leave /*egress, found right truncatable prime*/

<pre>

The largest left─truncatable prime ≤ 1000000 is 998443

The largest right─truncatable prime ≤ 1000000 is 739399

</pre>

 

=={{header|Ruby}}==

truncatable?(n) {|i| i.to_s[1..-1].to_i}

end

 

p primes.detect {|p| left_truncatable? p}

 

returns

The largest left truncatable prime less than 1000000 in base 10 is 998443

</pre>

 

=={{header|Sidef}}==

var p = %w(2 3 5 7);

var f = (

 

say t_prime(5, left: true)

{{out}}

<pre>

998443

739399

</pre>

 

=={{header|Tcl}}==

# Optimized version of the Sieve-of-Eratosthenes task solution

break

}

Output:

<pre>

searching for largest right-truncatable prime

FOUND:739399

</pre>

 

=={{header|VBScript}}==

start_time = Now

 

End If

End Function

 

{{Out}}

Largest RTP from 1..1000000: 739399

Elapse Time(seconds) : 49

</pre>

 

=={{header|XPL0}}==

 

func Prime(P); \Return true if P is a prime number

[IntOut(0, LeftTrunc); CrLf(0);

IntOut(0, RightTrunc); CrLf(0);

 

Output:

=={{header|zkl}}==

Using [[Extensible prime generator#zkl]] and a one meg bucket of bytes, construct a yes/no lookup table for all primes <= one million (<80,000).

 

var pTable=Data(million+1,Int).fill(0); // actually bytes, all zero

while(ns){ if(not pTable[ns]) return(False); ns=ns[1,*]; }

True

"%,d is a right truncatable prime".fmt(_).println();

[million..0,-1].filter1(leftTrunc):

{{out}}

<pre>