Substring primes: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (7 intermediate revisions by 6 users not shown) | |||
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 415:
373
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
function IsSubstringPrime(N: integer): boolean;
begin
if not IsPrime(N) then Result:=False
else if n < 10 then Result:=True
else if not IsPrime(N mod 100) then Result:=False
else if not IsPrime(N mod 10) then Result:=False
else if not IsPrime(N div 10) then Result:=False
else if n < 100 then Result:=True
else if not IsPrime(N div 100) then Result:=False
else if not IsPrime((N mod 100) div 10) then Result:=False
else Result:=True;
end;
procedure ShowSubtringPrimes(Memo: TMemo);
var N: integer;
begin
for N:=2 to 500-1 do
if IsSubstringPrime(N) then Memo.Lines.Add(IntToStr(N));
end;
</syntaxhighlight>
{{out}}
<pre>
2
3
5
7
23
37
53
73
373
Elapsed Time: 8.708 ms.
</pre>
=={{header|Factor}}==
Line 420 ⟶ 465:
{{trans|FreeBASIC}}
{{works with|Factor|0.99 2021-02-05}}
<
:: ssp? ( n -- ? )
Line 435 ⟶ 480:
} cond ;
500 <iota> [ ssp? ] filter .</
{{out}}
<pre>
Line 443 ⟶ 488:
=={{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 ⟶ 505:
if is_ssp(i) then print i;" ";
next i
print</
{{out}}<pre>2 3 5 7 23 37 53 73 373</pre>
Line 467 ⟶ 512:
{{libheader|Go-rcu}}
===Using a limit===
<
import (
Line 500 ⟶ 545:
fmt.Println("Found", len(sprimes), "primes < 500 where all substrings are also primes, namely:")
fmt.Println(sprimes)
}</
{{out}}
Line 509 ⟶ 554:
<br>
===Advanced===
<
import (
Line 544 ⟶ 589:
fmt.Println(discarded)
fmt.Println("\nTotal number of primality tests =", tests)
}</
{{out}}
Line 565 ⟶ 610:
See e.g. [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime`.
<
$out else . end;
Line 608 ⟶ 653:
"...",
( [verify] as $extra
| if $extra == [] then "done" else $extra end )</
{{out}}
<pre>
Line 619 ⟶ 664:
=={{header|Julia}}==
<
const pmask = primesmask(1, 1000)
Line 633 ⟶ 678:
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 ⟶ 712:
# 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 ⟶ 720:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
{{out}}
<pre>{2, 3, 5, 7, 23, 37, 53, 73, 373}</pre>
Line 682 ⟶ 727:
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 ⟶ 768:
echo "List of substring primes: ", result.join(" ")
echo "Number of primality tests: ", primeTestCount</
{{out}}
Line 730 ⟶ 775:
=={{header|Perl}}==
<
use strict; # https://rosettacode.org/wiki/Substring_primes
Line 748 ⟶ 793:
}
}
printf " %d" x %prime . "\n", sort {$a <=> $b} keys %prime;</
{{out}}
2 3 5 7 23 37 53 73 373
Line 755 ⟶ 800:
=={{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 ⟶ 828:
<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 791 ⟶ 836:
6 innocent bystanders falsly accused of being prime (15 tests in total): {237,27,3737,537,57,737}
</pre>
=={{header|Picat}}==
===Checking via substrings===
<syntaxhighlight lang="picat">% get all the substrings of a number
subs(N) = findall(S, (append(_Pre,S,_Post,N.to_string), S.len > 0) ).
go =>
Ps = [],
foreach(Prime in primes(500))
(foreach(N in subs(Prime) prime(N) end -> Ps := Ps ++ [Prime] ; true)
end,
println(Ps).</syntaxhighlight>
{{out}}
<pre>[2,3,5,7,23,37,53,73,373]</pre>
===Checking via predicate===
{{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.
<syntaxhighlight lang="picat">t(N,false) :-
not prime(N),!.
t(N,true) :-
N < 10,!.
t(N,false) :-
not prime(N mod 100), !.
t(N,false) :-
not prime(N mod 10),!.
t(N,false) :-
not prime(N // 10),!.
t(N,true) :-
N < 100,!.
t(N,false) :-
not prime(N // 100),!.
t(N,false) :-
not prime((N mod 100) // 10),!.
t(_N,true).
go2 =>
println(findall(N,(member(N,1..500),t(N,Status),Status==true))).</syntaxhighlight>
{{out}}
<pre>[2,3,5,7,23,37,53,73,373]</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku"
say gather while @p {
Line 799 ⟶ 887:
@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 821 ⟶ 909:
@p = ( @p X~ <3 7> ).grep: { !.ends-with(33|77) and .&spy-prime };
}
.say for :$prime-tests, :@non-primes;</
{{out}}
<pre>
Line 829 ⟶ 917:
=={{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 876 ⟶ 964:
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 888 ⟶ 976:
=={{header|Ring}}==
<
load "stdlib.ring"
Line 920 ⟶ 1,008:
see nl + "Found " + row + " numbers in which all substrings are primes" + nl
see "done..." + nl
</syntaxhighlight>
{{out}}
<pre>
Line 928 ⟶ 1,016:
Found 9 numbers in which all substrings are primes
done...
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">use primes::is_prime;
fn counted_prime_test() {
let mut number_of_prime_tests = 0;
let mut non_primes = vec![0; 0];
// start with 1 digit primes
let mut results: Vec<i32> = [2, 3, 5, 7].to_vec();
// check 2 digit candidates
for n in results.clone() {
for i in [3, 7].to_vec() {
if n != i {
let candidate = n * 10 + i;
if candidate < 100 {
number_of_prime_tests += 1;
if is_prime(candidate as u64) {
results.push(candidate);
} else {
non_primes.push(candidate);
}
}
}
}
}
// check 3 digit candidates
for n in results.clone() {
for i in [3, 7].to_vec() {
if 10 < n && n < 100 && n % 10 != i {
let candidate = n * 10 + i;
number_of_prime_tests += 1;
if is_prime(candidate as u64) {
results.push(candidate);
} else {
non_primes.push(candidate);
}
}
}
}
println!("Results: {results:?}.\nThe function isprime() was called {number_of_prime_tests} times.");
println!("Discarded nonprime candidates: {non_primes:?}");
println!("Because 237, 537, and 737 are excluded, we cannot generate any larger candidates from 373.");
}
fn main() {
counted_prime_test();
}
</syntaxhighlight>{{out}}
<pre>
Results: [2, 3, 5, 7, 23, 37, 53, 73, 373].
The function isprime() was called 10 times.
Discarded nonprime candidates: [27, 57, 237, 537, 737]
Because 237, 537, and 737 are already excluded, we cannot generate any larger candidates from 373.
</pre>
=={{header|RPL}}==
≪ { 2 3 5 7 } { } 0 1 → winners losers tests index
≪ 3
'''DO'''
winners index GET 10 * OVER + SWAP
'''IF''' 7 == '''THEN''' 3 'index' 1 STO+ '''ELSE''' 7 '''END'''
SWAP 1 CF
'''IF''' DUP 3 MOD OVER 100 MOD 11 MOD AND '''THEN'''
'''IF''' DUP ISPRIME? 'tests' 1 STO+ 1 FS '''THEN'''
'''IF''' DUP 100 MOD ISPRIME? 'tests' 1 STO+ 1 FS '''THEN''' 'winners' OVER STO+ 1 CF
'''END END END'''
'''IF''' 1 FS? '''THEN''' 'losers' OVER STO+ '''END'''
'''UNTIL''' 500 > '''END'''
DROP winners losers tests
≫ ≫ '<span style="color:blue">A085823</span>' STO
{{out}}
<pre>
3: { 2 3 5 7 23 37 53 73 373 }
2: { }
1: 10
</pre>
=={{header|Sidef}}==
Generic solution for any base >= 2.
<
var parts = []
Line 938 ⟶ 1,103:
for j in (indices) {
parts << [array
i = j+1
}
Line 994 ⟶ 1,159:
for base in (2..20) {
say "base = #{base}: #{substring_primes(base)}"
}</
{{out}}
<pre>
Line 1,022 ⟶ 1,187:
===Using a limit===
<
var primes = Int.primeSieve(499)
var sprimes = []
Line 1,039 ⟶ 1,204:
}
System.print("Found %(sprimes.count) primes < 500 where all substrings are also primes, namely:")
System.print(sprimes)</
{{out}}
Line 1,049 ⟶ 1,214:
===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,073 ⟶ 1,238:
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,087 ⟶ 1,252:
=={{header|XPL0}}==
<
int N, I;
[if N <= 1 then return false;
Line 1,105 ⟶ 1,270:
[IntOut(0, N); ChOut(0, ^ )];
];
]</
{{out}}
| |||