Substring primes: Difference between revisions

{{trans|Go}}

 

I n == 2

R 1B

print("\nThe following numbers were also tested for primality but found to be composite:")

print(discarded)

 

{{out}}

=={{header|Action!}}==

{{libheader|Action! Sieve of Eratosthenes}}

 

BYTE FUNC IsSubstringPrime(INT x BYTE ARRAY primes)

FI

OD

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Substring_primes.png Screenshot from Atari 8-bit computer]

=={{header|ALGOL 68}}==

{{libheader|ALGOL 68-primes}}

# find the primes of interest #

PR read "primes.incl.a68" PR

FI

OD

{{out}}

<pre>

=={{header|ALGOL W}}==

starts with a hardcoded list of 1 digit primes ( 2, 3, 5, 7 ) and constructs the remaining members of the sequence (in order) using the observations that the final digit must be prime and can't be 2 or 5 or the number wouldn't be prime. Additionally, the final digit pair cannot be 33 or 77 as these are divisible by 11.

% sets p( 1 :: n ) to a sieve of primes up to n %

procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;

write( i_w := 1, s_w := 0, "Found ", sCount, " substring primes" )

end

{{out}}

<pre>

</pre>

=={{header|AWK}}==

# syntax: GAWK -f SUBSTRING_PRIMES.AWK

# converted from FreeBASIC

return(1)

}

{{out}}

<pre>

=={{header|BASIC}}==

==={{header|BASIC256}}===

if v < 2 then return False

if v mod 2 = 0 then return v = 2

if isSubstringPrime(i) then print i; " ";

next i

{{out}}

<pre>

 

==={{header|PureBasic}}===

If v <= 1 : ProcedureReturn #False

ElseIf v < 4 : ProcedureReturn #True

Next i

Input()

{{out}}

<pre>

 

==={{header|Yabasic}}===

if v < 2 then return False : fi

if mod(v, 2) = 0 then return v = 2 : fi

if isSubstringPrime(i) then print i, " "; : fi

next i

{{out}}

<pre>

 

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

#include <vector>

 

}

return 0;

 

{{out}}

{{trans|FreeBASIC}}

{{works with|Factor|0.99 2021-02-05}}

 

:: ssp? ( n -- ? )

} cond ;

 

{{out}}

<pre>

=={{header|FreeBASIC}}==

Since this is limited to one, two, or three-digit numbers I will be a bit cheeky.

 

function is_ssp(n as uinteger) as boolean

if is_ssp(i) then print i;" ";

next i

{{out}}<pre>2 3 5 7 23 37 53 73 373</pre>

 

{{libheader|Go-rcu}}

===Using a limit===

 

import (

fmt.Println("Found", len(sprimes), "primes < 500 where all substrings are also primes, namely:")

fmt.Println(sprimes)

 

{{out}}

<br>

===Advanced===

 

import (

fmt.Println(discarded)

fmt.Println("\nTotal number of primality tests =", tests)

 

{{out}}

 

See e.g. [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime`.

$out else . end;

 

"...",

( [verify] as $extra

{{out}}

<pre>

 

=={{header|Julia}}==

 

const pmask = primesmask(1, 1000)

 

println(filter(isA085823, 1:1000))

<pre>

[2, 3, 5, 7, 23, 37, 53, 73, 373]

</pre>

=== Advanced task ===

 

const nt, nons = [0], Int[]

 

# Because 237, 537, and 737 are already excluded, we cannot generate any larger candidates from 373.

<pre>

Results: [2, 3, 5, 7, 23, 37, 53, 73, 373].

 

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

{{out}}

<pre>{2, 3, 5, 7, 23, 37, 53, 73, 373}</pre>

The algorithm we use solves the advanced task as it finds the substring primes with only 11 primality tests. Note that, if we limit to numbers with at most three digits, 10 tests are sufficient. As we don’t use this limitation, we need one more test to detect than 3737 is not prime.

 

 

type

 

echo "List of substring primes: ", result.join(" ")

 

{{out}}

 

=={{header|Perl}}==

 

use strict; # https://rosettacode.org/wiki/Substring_primes

}

}

{{out}}

2 3 5 7 23 37 53 73 373

=={{header|Phix}}==

This tests a total of just 15 numbers for primality.

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

<span style="color: #000080;font-style:italic;">--sequence tested = {}

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d innocent bystanders falsly accused of being prime (%d tests in total): %V\n"</span><span style="color: #0000FF;">,</span>

<span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">tested</span><span style="color: #0000FF;">})</span>

<small>[1]It is possible that the compiler could be improved to avoid the need for those deep_copy().</small><br>

<small>The other seven commented out lines show a different way to avoid any use of deep_copy().</small>

=={{header|Picat}}==

===Checking via substrings===

subs(N) = findall(S, (append(_Pre,S,_Post,N.to_string), S.len > 0) ).

 

(foreach(N in subs(Prime) prime(N) end -> Ps := Ps ++ [Prime] ; true)

end,

 

{{out}}

{{trans|AWK}}

Here we must use cut (<code>!</code>) to ensure that the test does not continue after a satisfied test. This is a "red cut" (i.e. removing it would change the logic of the program) and these should be avoided if possible.

not prime(N),!.

t(N,true) :-

 

go2 =>

 

{{out}}

 

=={{header|Raku}}==

 

say gather while @p {

 

@p = ( @p X~ <3 7> ).grep: { .is-prime and .substr(*-2,2).is-prime }

{{out}}

<pre>

(2 3 5 7 23 37 53 73 373)</pre>

===Stretch Goal===

my @non-primes;

sub spy-prime ($n) {

@p = ( @p X~ <3 7> ).grep: { !.ends-with(33|77) and .&spy-prime };

}

{{out}}

<pre>

 

=={{header|REXX}}==

parse arg n cols . /*obtain optional argument from the CL.*/

if n=='' | n=="," then n= 500 /*Not specified? Then use the default.*/

end /*k*/ /* [↑] only process numbers ≤ √ J */

#= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

 

=={{header|Ring}}==

load "stdlib.ring"

 

see nl + "Found " + row + " numbers in which all substrings are primes" + nl

see "done..." + nl

{{out}}

<pre>

=={{header|Sidef}}==

Generic solution for any base >= 2.

 

var parts = []

for base in (2..20) {

say "base = #{base}: #{substring_primes(base)}"

{{out}}

<pre>

 

===Using a limit===

var primes = Int.primeSieve(499)

var sprimes = []

}

System.print("Found %(sprimes.count) primes < 500 where all substrings are also primes, namely:")

 

{{out}}

===Advanced===

This follows the logic in the OEIS A085823 comments.

 

var results = [2, 3, 5, 7] // number must begin with a prime digit

System.print("\nThe following numbers were also tested for primality but found to be composite:")

System.print(discarded)

 

{{out}}

 

=={{header|XPL0}}==

int N, I;

[if N <= 1 then return false;

[IntOut(0, N); ChOut(0, ^ )];

];

 

{{out}}