Substring primes: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 15:
{{trans|Go}}
<
I n == 2
R 1B
Line 47:
print("\nThe following numbers were also tested for primality but found to be composite:")
print(discarded)
print("\nTotal number of primality tests = "tests)</
{{out}}
Line 62:
=={{header|Action!}}==
{{libheader|Action! Sieve of Eratosthenes}}
<
BYTE FUNC IsSubstringPrime(INT x BYTE ARRAY primes)
Line 99:
FI
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Substring_primes.png Screenshot from Atari 8-bit computer]
Line 116:
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-primes}}
<
# find the primes of interest #
PR read "primes.incl.a68" PR
Line 135:
FI
OD
END</
{{out}}
<pre>
Line 143:
=={{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 ) ;
Line 192:
write( i_w := 1, s_w := 0, "Found ", sCount, " substring primes" )
end
end.</
{{out}}
<pre>
Line 199:
</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SUBSTRING_PRIMES.AWK
# converted from FreeBASIC
Line 236:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 246:
=={{header|BASIC}}==
==={{header|BASIC256}}===
<
if v < 2 then return False
if v mod 2 = 0 then return v = 2
Line 272:
if isSubstringPrime(i) then print i; " ";
next i
end</
{{out}}
<pre>
Line 279:
==={{header|PureBasic}}===
<
If v <= 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
Line 316:
Next i
Input()
CloseConsole()</
{{out}}
<pre>
Line 323:
==={{header|Yabasic}}===
<
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
Line 349:
if isSubstringPrime(i) then print i, " "; : fi
next i
end</
{{out}}
<pre>
Line 357:
=={{header|C++}}==
<
#include <vector>
Line 401:
}
return 0;
}</
{{out}}
Line 420:
{{trans|FreeBASIC}}
{{works with|Factor|0.99 2021-02-05}}
<
:: ssp? ( n -- ? )
Line 435:
} cond ;
500 <iota> [ ssp? ] filter .</
{{out}}
<pre>
Line 443:
=={{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
Line 460:
if is_ssp(i) then print i;" ";
next i
print</
{{out}}<pre>2 3 5 7 23 37 53 73 373</pre>
Line 467:
{{libheader|Go-rcu}}
===Using a limit===
<
import (
Line 500:
fmt.Println("Found", len(sprimes), "primes < 500 where all substrings are also primes, namely:")
fmt.Println(sprimes)
}</
{{out}}
Line 509:
<br>
===Advanced===
<
import (
Line 544:
fmt.Println(discarded)
fmt.Println("\nTotal number of primality tests =", tests)
}</
{{out}}
Line 565:
See e.g. [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime`.
<
$out else . end;
Line 608:
"...",
( [verify] as $extra
| if $extra == [] then "done" else $extra end )</
{{out}}
<pre>
Line 619:
=={{header|Julia}}==
<
const pmask = primesmask(1, 1000)
Line 633:
println(filter(isA085823, 1:1000))
</
<pre>
[2, 3, 5, 7, 23, 37, 53, 73, 373]
</pre>
=== Advanced task ===
<
const nt, nons = [0], Int[]
Line 667:
# 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].
Line 675:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
{{out}}
<pre>{2, 3, 5, 7, 23, 37, 53, 73, 373}</pre>
Line 682:
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
Line 723:
echo "List of substring primes: ", result.join(" ")
echo "Number of primality tests: ", primeTestCount</
{{out}}
Line 730:
=={{header|Perl}}==
<
use strict; # https://rosettacode.org/wiki/Substring_primes
Line 748:
}
}
printf " %d" x %prime . "\n", sort {$a <=> $b} keys %prime;</
{{out}}
2 3 5 7 23 37 53 73 373
Line 755:
=={{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 = {}
Line 783:
<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>
Line 794:
=={{header|Picat}}==
===Checking via substrings===
<
subs(N) = findall(S, (append(_Pre,S,_Post,N.to_string), S.len > 0) ).
Line 802:
(foreach(N in subs(Prime) prime(N) end -> Ps := Ps ++ [Prime] ; true)
end,
println(Ps).</
{{out}}
Line 810:
{{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) :-
Line 829:
go2 =>
println(findall(N,(member(N,1..500),t(N,Status),Status==true))).</
{{out}}
Line 836:
=={{header|Raku}}==
<syntaxhighlight lang="raku"
say gather while @p {
Line 842:
@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===
<syntaxhighlight lang="raku"
my @non-primes;
sub spy-prime ($n) {
Line 864:
@p = ( @p X~ <3 7> ).grep: { !.ends-with(33|77) and .&spy-prime };
}
.say for :$prime-tests, :@non-primes;</
{{out}}
<pre>
Line 872:
=={{header|REXX}}==
<
parse arg n cols . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 500 /*Not specified? Then use the default.*/
Line 919:
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return</
{{out|output|text= when using the default inputs:}}
<pre>
Line 931:
=={{header|Ring}}==
<
load "stdlib.ring"
Line 963:
see nl + "Found " + row + " numbers in which all substrings are primes" + nl
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 975:
=={{header|Sidef}}==
Generic solution for any base >= 2.
<
var parts = []
Line 1,037:
for base in (2..20) {
say "base = #{base}: #{substring_primes(base)}"
}</
{{out}}
<pre>
Line 1,065:
===Using a limit===
<
var primes = Int.primeSieve(499)
var sprimes = []
Line 1,082:
}
System.print("Found %(sprimes.count) primes < 500 where all substrings are also primes, namely:")
System.print(sprimes)</
{{out}}
Line 1,092:
===Advanced===
This follows the logic in the OEIS A085823 comments.
<
var results = [2, 3, 5, 7] // number must begin with a prime digit
Line 1,116:
System.print("\nThe following numbers were also tested for primality but found to be composite:")
System.print(discarded)
System.print("\nTotal number of primality tests = %(tests)")</
{{out}}
Line 1,130:
=={{header|XPL0}}==
<
int N, I;
[if N <= 1 then return false;
Line 1,148:
[IntOut(0, N); ChOut(0, ^ )];
];
]</
{{out}}
|