Rosetta Code

Substring primes: Difference between revisions

Page Discussion

Substring primes (view source)

Revision as of 16:48, 10 February 2024

10,107 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(14 intermediate revisions by 10 users not shown)
Line 11:
Solve by testing at most 15 numbers for primality. Show a list of all numbers tested that were not prime.
<br><br>
 
=={{header|11l}}==
{{trans|Go}}
 
<syntaxhighlight lang="11l">F is_prime(n)
I n == 2
R 1B
I n < 2 | n % 2 == 0
R 0B
L(i) (3 .. Int(sqrt(n))).step(2)
I n % i == 0
R 0B
R 1B
 
V results = [2, 3, 5, 7]
V odigits = [3, 7]
[Int] discarded
V tests = 4
 
V i = 0
L i < results.len
V r = results[i]
i++
L(od) odigits
I (r % 10) != od
V n = r * 10 + od
I is_prime(n)
results.append(n)
E
discarded.append(n)
tests++
 
print(‘There are ’results.len‘ primes where all substrings are also primes, namely:’)
print(results)
print("\nThe following numbers were also tested for primality but found to be composite:")
print(discarded)
print("\nTotal number of primality tests = "tests)</syntaxhighlight>
 
{{out}}
<pre>
There are 9 primes where all substrings are also primes, namely:
[2, 3, 5, 7, 23, 37, 53, 73, 373]
 
The following numbers were also tested for primality but found to be composite:
[27, 57, 237, 537, 737, 3737]
 
Total number of primality tests = 15
</pre>
 
=={{header|Action!}}==
{{libheader|Action! Sieve of Eratosthenes}}
<syntaxhighlight lang="action!">INCLUDE "H6:SIEVE.ACT"
 
BYTE FUNC IsSubstringPrime(INT x BYTE ARRAY primes)
CHAR ARRAY s(4),tmp(4)
INT len,start,sub
 
IF primes(x)=0 THEN
RETURN (0)
FI
 
StrI(x,s)
FOR len=1 TO s(0)-1
DO
FOR start=1 TO s(0)-len+1
DO
SCopyS(tmp,s,start,start+len-1)
sub=ValI(tmp)
IF primes(sub)=0 THEN
RETURN (0)
FI
OD
OD
RETURN (1)
 
PROC Main()
DEFINE MAX="499"
BYTE ARRAY primes(MAX+1)
INT i
 
Put(125) PutE() ;clear the screen
Sieve(primes,MAX+1)
FOR i=2 TO MAX
DO
IF IsSubstringPrime(i,primes) THEN
PrintIE(i)
FI
OD
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Substring_primes.png Screenshot from Atari 8-bit computer]
<pre>
2
3
5
7
23
37
53
73
373
</pre>
 
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-primes}}
<langsyntaxhighlight lang="algol68">BEGIN # find primes where all substrings of the digits are prime #
# find the primes of interest #
PR read "primes.incl.a68" PR
Line 25 ⟶ 127:
INT n := p;
WHILE is substring AND n > 0 DO
INTis sub digitssubstring := prime[ n MOD d ];
is substring := IF sub digits = 0 THEN FALSE ELSE prime[ sub digits ] FI;
n OVERAB 10
OD;
Line 34 ⟶ 135:
FI
OD
END</langsyntaxhighlight>
{{out}}
<pre>
Line 42 ⟶ 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.
<langsyntaxhighlight lang="algolw">begin % find primes where every substring of the digits is also priome %
% sets p( 1 :: n ) to a sieve of primes up to n %
procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
Line 91 ⟶ 192:
write( i_w := 1, s_w := 0, "Found ", sCount, " substring primes" )
end
end.</langsyntaxhighlight>
{{out}}
<pre>
Line 98 ⟶ 199:
</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
<lang AWK>
# syntax: GAWK -f SUBSTRING_PRIMES.AWK
# converted from FreeBASIC
Line 135 ⟶ 236:
return(1)
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 141 ⟶ 242:
SubString Primes 1-500: 9
</pre>
 
 
=={{header|BASIC}}==
==={{header|BASIC256}}===
<syntaxhighlight lang="freebasic">function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function
 
function isSubstringPrime (n)
if not isPrime(n) then return False
if n < 10 then return True
if not isPrime(n mod 100) then return False
if not isPrime(n mod 10) then return False
if not isPrime(n \ 10) then return False
if n < 100 then return True
if not isPrime(n \ 100) then return False
if not isPrime((n mod 100) \ 10) then return False
return True
end function
 
for i = 1 to 500
if isSubstringPrime(i) then print i; " ";
next i
end</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC.
</pre>
 
==={{header|PureBasic}}===
<syntaxhighlight lang="purebasic">Procedure isPrime(v.i)
If v <= 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
ElseIf v % 2 = 0 : ProcedureReturn #False
ElseIf v < 9 : ProcedureReturn #True
ElseIf v % 3 = 0 : ProcedureReturn #False
Else
Protected r = Round(Sqr(v), #PB_Round_Down)
Protected f = 5
While f <= r
If v % f = 0 Or v % (f + 2) = 0
ProcedureReturn #False
EndIf
f + 6
Wend
EndIf
ProcedureReturn #True
EndProcedure
 
Procedure isSubstringPrime (n)
If Not isPrime(n) : ProcedureReturn #False
ElseIf n < 10 : ProcedureReturn #True
ElseIf Not isPrime(n % 100) : ProcedureReturn #False
ElseIf Not isPrime(n % 10) : ProcedureReturn #False
ElseIf Not isPrime(n / 10) : ProcedureReturn #False
ElseIf n < 100 : ProcedureReturn #True
ElseIf Not isPrime(n / 100) : ProcedureReturn #False
ElseIf Not isPrime((n % 100)/10) : ProcedureReturn #False
EndIf
ProcedureReturn #True
EndProcedure
 
OpenConsole()
For i.i = 1 To 500
If isSubstringPrime(i) : Print(Str(i) + " ") : EndIf
Next i
Input()
CloseConsole()</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC.
</pre>
 
==={{header|Yabasic}}===
<syntaxhighlight lang="freebasic">sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
 
sub isSubstringPrime (n)
if not isPrime(n) then return False : fi
if n < 10 then return True : fi
if not isPrime(mod(n, 100)) then return False : fi
if not isPrime(mod(n, 10)) then return False : fi
if not isPrime(int(n / 10)) then return False : fi
if n < 100 then return True : fi
if not isPrime(int(n / 100)) then return False : fi
if not isPrime(int(mod(n, 100))/10) then return False : fi
return True
end sub
 
for i = 1 to 500
if isSubstringPrime(i) then print i, " "; : fi
next i
end</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de FreeBASIC.
</pre>
 
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <iostream>
#include <vector>
 
Line 187 ⟶ 401:
}
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 201 ⟶ 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 206 ⟶ 465:
{{trans|FreeBASIC}}
{{works with|Factor|0.99 2021-02-05}}
<langsyntaxhighlight lang="factor">USING: combinators kernel math math.primes prettyprint sequences ;
 
:: ssp? ( n -- ? )
Line 221 ⟶ 480:
} cond ;
 
500 <iota> [ ssp? ] filter .</langsyntaxhighlight>
{{out}}
<pre>
Line 229 ⟶ 488:
=={{header|FreeBASIC}}==
Since this is limited to one, two, or three-digit numbers I will be a bit cheeky.
<langsyntaxhighlight lang="freebasic">#include "isprime.bas"
 
function is_ssp(n as uinteger) as boolean
Line 246 ⟶ 505:
if is_ssp(i) then print i;" ";
next i
print</langsyntaxhighlight>
{{out}}<pre>2 3 5 7 23 37 53 73 373</pre>
 
Line 253 ⟶ 512:
{{libheader|Go-rcu}}
===Using a limit===
<langsyntaxhighlight lang="go">package main
 
import (
Line 286 ⟶ 545:
fmt.Println("Found", len(sprimes), "primes < 500 where all substrings are also primes, namely:")
fmt.Println(sprimes)
}</langsyntaxhighlight>
 
{{out}}
Line 295 ⟶ 554:
<br>
===Advanced===
<langsyntaxhighlight lang="go">package main
 
import (
Line 330 ⟶ 589:
fmt.Println(discarded)
fmt.Println("\nTotal number of primality tests =", tests)
}</langsyntaxhighlight>
 
{{out}}
Line 351 ⟶ 610:
 
See e.g. [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime`.
<langsyntaxhighlight lang="jq">def emit_until(cond; stream): label $out | stream | if cond then break
$out else . end;
 
Line 394 ⟶ 653:
"...",
( [verify] as $extra
| if $extra == [] then "done" else $extra end )</langsyntaxhighlight>
{{out}}
<pre>
Line 405 ⟶ 664:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
const pmask = primesmask(1, 1000)
Line 419 ⟶ 678:
 
println(filter(isA085823, 1:1000))
</langsyntaxhighlight>{{out}}
<pre>
[2, 3, 5, 7, 23, 37, 53, 73, 373]
</pre>
=== Advanced task ===
<langsyntaxhighlight lang="julia">using Primes
 
const nt, nons = [0], Int[]
Line 453 ⟶ 712:
 
# Because 237, 537, and 737 are already excluded, we cannot generate any larger candidates from 373.
</langsyntaxhighlight>{{out}}
<pre>
Results: [2, 3, 5, 7, 23, 37, 53, 73, 373].
Line 461 ⟶ 720:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">Select[Range[500], PrimeQ[#] && AllTrue[Subsequences[IntegerDigits[#], {1, \[Infinity]}], FromDigits /* PrimeQ] &]</langsyntaxhighlight>
{{out}}
<pre>{2, 3, 5, 7, 23, 37, 53, 73, 373}</pre>
Line 468 ⟶ 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.
 
<langsyntaxhighlight Nimlang="nim">import sequtils, strutils
 
type
Line 509 ⟶ 768:
 
echo "List of substring primes: ", result.join(" ")
echo "Number of primality tests: ", primeTestCount</langsyntaxhighlight>
 
{{out}}
Line 516 ⟶ 775:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Substring_primes
Line 534 ⟶ 793:
}
}
printf " %d" x %prime . "\n", sort {$a <=> $b} keys %prime;</langsyntaxhighlight>
{{out}}
2 3 5 7 23 37 53 73 373
Line 541 ⟶ 800:
=={{header|Phix}}==
This tests a total of just 15 numbers for primality.
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">--sequence tested = {}
Line 569 ⟶ 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>
<!--</langsyntaxhighlight>-->
<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 577 ⟶ 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" perl6line>my @p = (^10).grep: *.is-prime;
 
say gather while @p {
Line 585 ⟶ 887:
 
@p = ( @p X~ <3 7> ).grep: { .is-prime and .substr(*-2,2).is-prime }
}</langsyntaxhighlight>
{{out}}
<pre>
(2 3 5 7 23 37 53 73 373)</pre>
===Stretch Goal===
<syntaxhighlight lang="raku" perl6line>my $prime-tests = 0;
my @non-primes;
sub spy-prime ($n) {
Line 607 ⟶ 909:
@p = ( @p X~ <3 7> ).grep: { !.ends-with(33|77) and .&spy-prime };
}
.say for :$prime-tests, :@non-primes;</langsyntaxhighlight>
{{out}}
<pre>
Line 615 ⟶ 917:
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX program finds/shows decimal primes where all substrings are also prime, N < 500.*/
parse arg n cols . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 500 /*Not specified? Then use the default.*/
Line 662 ⟶ 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</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
Line 674 ⟶ 976:
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
load "stdlib.ring"
 
Line 706 ⟶ 1,008:
see nl + "Found " + row + " numbers in which all substrings are primes" + nl
see "done..." + nl
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 714 ⟶ 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.
<langsyntaxhighlight lang="ruby">func split_at_indices(array, indices) {
 
var parts = []
Line 724 ⟶ 1,103:
 
for j in (indices) {
parts << [array.slice([i, ..j)]]
i = j+1
}
Line 780 ⟶ 1,159:
for base in (2..20) {
say "base = #{base}: #{substring_primes(base)}"
}</langsyntaxhighlight>
{{out}}
<pre>
Line 808 ⟶ 1,187:
 
===Using a limit===
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
var primes = Int.primeSieve(499)
var sprimes = []
Line 825 ⟶ 1,204:
}
System.print("Found %(sprimes.count) primes < 500 where all substrings are also primes, namely:")
System.print(sprimes)</langsyntaxhighlight>
 
{{out}}
Line 835 ⟶ 1,214:
===Advanced===
This follows the logic in the OEIS A085823 comments.
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
 
var results = [2, 3, 5, 7] // number must begin with a prime digit
Line 859 ⟶ 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)")</langsyntaxhighlight>
 
{{out}}
Line 873 ⟶ 1,252:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">func IsPrime(N); \Return 'true' if N is a prime number
int N, I;
[if N <= 1 then return false;
Line 891 ⟶ 1,270:
[IntOut(0, N); ChOut(0, ^ )];
];
]</langsyntaxhighlight>
 
{{out}}
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/310988...354719"