Prime numbers which contain 123
- Task
Find those primes n whose decimal representation contains the consecutive digits 123, where n < 100,000.
- Stretch goal
As above, but only show the count of those primes n that contain the (above) string, where n < 1,000,000.
11l
F is_prime(a)
I a == 2
R 1B
I a < 2 | a % 2 == 0
R 0B
L(i) (3 .. Int(sqrt(a))).step(2)
I a % i == 0
R 0B
R 1B
F is_prime123(n)
R ‘123’ C String(n) & is_prime(n)
V c = 0
L(n) 100'000
I is_prime123(n)
c++
print(‘#5’.format(n), end' I c % 8 == 0 {"\n"} E ‘ ’)
print()
print(‘Found ’c‘ "123" primes less than 100000’)
c = 0
L(n) 1'000'000
I is_prime123(n)
c++
print()
print(‘Found ’c‘ "123" primes less than 1000000’)
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Found 46 "123" primes less than 100000 Found 451 "123" primes less than 1000000
ALGOL 68
BEGIN # find primes whose decimal representation contains 123 #
INT max prime = 1 000 000;
# sieve the primes to max prime #
PR read "primes.incl.a68" PR
[]BOOL prime = PRIMESIEVE max prime;
# find the appropriate primes #
# as observed by the Wren sample, the primes must have a least 4 digits #
INT show max = 100 000;
INT p123 count := 0;
FOR n FROM 1001 TO UPB prime DO
IF prime[ n ] THEN
# have a prime #
BOOL has 123 := FALSE;
INT v := n;
WHILE v >= 123 AND NOT ( has 123 := v MOD 1000 = 123 ) DO
v OVERAB 10
OD;
IF has 123 THEN
# the prime contains "123" #
p123 count +:= 1;
IF n <= show max THEN
print( ( whole( n, -7 ) ) );
IF p123 count MOD 12 = 0 THEN print( ( newline ) ) FI
FI
FI
FI;
IF n = 100 000 THEN
print( ( newline, "Found ", whole( p123 count, 0 ), " ""123"" primes below ", whole( show max, 0 ), newline ) )
FI
OD;
print( ( newline, "Found ", whole( p123 count, 0 ), " ""123"" primes below ", whole( UPB prime, 0 ), newline ) )
END
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Found 46 "123" primes below 100000 Found 451 "123" primes below 1000000
Arturo
upTo100K: select select 2..99999 => odd? => prime?
upTo1M: upTo100K ++ select select 100001..999999 => odd? => prime?
contains123?: function [x] -> contains? to :string x "123"
loop split.every:10 select upTo100K => contains123? 'a ->
print map a => [pad to :string & 5]
print ""
print ["'123' Numbers < 1000000:" size select upTo1M => contains123?]
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 '123' Numbers < 1000000: 451
AWK
# syntax: GAWK -f PRIME_NUMBERS_WHICH_CONTAIN_123.AWK
BEGIN {
start = 1
stop = 99999
for (i=start; i<=stop; i++) {
if (is_prime(i) && i ~ /123/) {
printf("%6d%1s",i,++count%10?"":"\n")
}
}
printf("\nPrimes with '123' %d-%d: %d\n",start,stop,count)
stop = 999999
for (i=100000; i<=stop; i++) {
if (is_prime(i) && i ~ /123/) {
count++
}
}
printf("\nPrimes with '123' %d-%d: %d\n",start,stop,count)
exit(0)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Primes with '123' 1-99999: 46 Primes with '123' 1-999999: 451
BASIC256
global columna
print "Prime numbers which contain 123"
print
limite = 100000
call prime(limite, true)
print : print
print "Found "; columna; " prime numbers below "; limite
limite = 1e6
call prime(limite, false)
print : print
print "Found "; columna; " prime numbers below "; int(limite)
end
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
subroutine prime(limite, mostrar)
columna = 0
for n = 1 to limite
strn$ = string(n)
if isPrime(n) and instr(strn$, "123") > 0 then
columna += 1
if mostrar then
print rjust(string(n), 7);
if columna mod 8 = 0 then print
end if
endif
next n
end subroutine
- Output:
Same as FreeBASIC entry.
C++
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
bool isPrime( int number ) {
if ( number < 2 ) {
return false ;
}
int stop = std::sqrt( static_cast<double>( number ) ) ;
for ( int i = 2 ; i <= stop ; ++i )
if ( number % i == 0 )
return false ;
return true ;
}
bool condition( int n ) {
std::string numberstring { std::to_string( n ) } ;
return isPrime( n ) && numberstring.find( "123" ) != std::string::npos ;
}
int main( ) {
std::vector<int> wantedPrimes ;
for ( int i = 1 ; i < 100000 ; i++ ) {
if ( condition( i ) )
wantedPrimes.push_back( i ) ;
}
int count = 0 ;
for ( int i : wantedPrimes ) {
std::cout << i << ' ' ;
count++ ;
if ( count % 10 == 0 ) {
std::cout << std::endl ;
}
}
count = wantedPrimes.size( ) ;
for ( int i = wantedPrimes.back( ) + 1 ; i < 1000000 ; i++ ) {
if ( condition ( i ) )
count++ ;
}
std::cout << std::endl ;
std::cout << "There are " << count << " such numbers below 1000000!\n" ;
return 0 ;
}
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 There are 451 such numbers below 1000000!
Clojure
(ns primes-found-app
(:require [clojure.string :as str])
(:gen-class))
(defn is-prime? [n]
(if (< 1 n)
(empty? (filter #(= 0 (mod n %)) (range 2 n)))
false))
(defn get-prime-numbers [n]
(filter is-prime? (take n (range))))
(defn numbers-to-str [xs]
(map #(str %) xs))
(defn is-includes-123? [s]
(str/includes? s "123"))
(defn solution [number]
(->>
(get-prime-numbers number)
(numbers-to-str)
(filter is-includes-123?)))
(defn main []
(let [result (count (solution 1000000))]
(prn (solution 100000))
(format "There are %d primes that contain '123' below 1000000." result)
))
(main)
- Output:
("1123" "1231" "1237" "8123" "11239" "12301" "12323" "12329" "12343" "12347" "12373" "12377" "12379" "12391" "17123" "20123" "22123" "28123" "29123" "31123" "31231" "31237" "34123" "37123" "40123" "41231" "41233" "44123" "47123" "49123" "50123" "51239" "56123" "59123" "61231" "64123" "65123" "70123" "71233" "71237" "76123" "81233" "81239" "89123" "91237" "98123") "There are 451 primes that contain '123' below 1000000."
CLU
isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0=0 then return(s) end
x1: int := (x0 + s/x0)/2
while x1 < x0 do
x0 := x1
x1 := (x0 + s/x0)/2
end
return(x0)
end isqrt
sieve = proc (n: int) returns (array[bool])
prime: array[bool] := array[bool]$fill(2,n-1,true)
for p: int in int$from_to(2,isqrt(n)) do
if prime[p] then
for c: int in int$from_to_by(p*p,n,p) do
prime[c] := false
end
end
end
return(prime)
end sieve
start_up = proc ()
po: stream := stream$primary_output()
count: int := 0
prime: array[bool] := sieve(1000000)
for p: int in array[bool]$indexes(prime) do
if ~prime[p] then continue end
if string$indexs("123", int$unparse(p))=0 then continue end
count := count + 1
if p < 100000 then
stream$putright(po, int$unparse(p), 7)
if count//10=0 then stream$putl(po, "") end
end
end
stream$putl(po, "\nThere are " || int$unparse(count)
|| " primes that contain '123' below 1,000,000.")
end start_up
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 There are 451 primes that contain '123' below 1,000,000.
Delphi
procedure ShowPrimesWith123(Memo: TMemo);
var N,Sum,Cnt1,Cnt2: integer;
var NS,S: string;
begin
Cnt1:=0;
Cnt2:=0;
Sum:=0;
for N:=123 to 1000000-1 do
if IsPrime(N) then
begin
NS:=IntToStr(N);
if Pos('123',NS)>0 then
begin
Inc(Cnt1);
if N<100000 then
begin
Inc(Cnt2);
S:=S+Format('%6d',[N]);
If (Cnt2 mod 8)=0 then S:=S+CRLF;
end;
end;
end;
Memo.Lines.Add(S);
Memo.Lines.Add('Count < 100,000 = '+IntToStr(Cnt2));
Memo.Lines.Add('Count < 1,000,000 = '+IntToStr(Cnt1));
end;
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Count < 100,000 = 46 Count < 1,000,000 = 451 Elapsed Time: 147.996 ms.
EasyLang
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
fastfunc nextprim prim .
repeat
prim += 1
until isprim prim = 1
.
return prim
.
func dig123 n .
while n > 0
if n mod 1000 = 123
return 1
.
n = n div 10
.
return 0
.
prim = 2
repeat
if dig123 prim = 1
write prim & " "
.
prim = nextprim prim
until prim >= 100000
.
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123
F#
This task uses Extensible Prime Generator (F#).
// Numbers containing 123. Nigel Galloway: July 14th., 2021
let rec fN g=if g%1000=123 then true else if g<1230 then false else fN(g/10)
primes32()|>Seq.takeWhile((>)100000)|>Seq.filter fN|>Seq.iter(printf "%d "); printfn ""
printfn "Count to 1 million is %d" (primes32()|>Seq.takeWhile((>)1000000)|>Seq.filter fN|>Seq.length)
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Count to 1 million is 451
FreeBASIC
Dim Shared As Integer column
Function isPrime(Byval ValorEval As Integer) As Boolean
If ValorEval <= 1 Then Return False
For i As Integer = 2 To Int(Sqr(ValorEval))
If ValorEval Mod i = 0 Then Return False
Next i
Return True
End Function
Sub prime(limite As Long, mostrar As Boolean)
column = 0
For n As Integer = 1 To limite
Dim As String strn = Str(n)
If isPrime(n) And Instr(strn,"123") > 0 Then
column += 1
If mostrar Then
Print Using " ##### "; n;
If (column Mod 8) = 0 Then Print
End If
End If
Next n
End Sub
Print !"N£meros primos que contienen 123:\n"
Dim As Long limite = 1e5
prime(limite, true)
Print !"\n\n\Encontrados "; column; " n£meros primos por debajo de"; limite
limite = 1e6
prime(limite, false)
Print !"\n\n\Encontrados "; column; " n£meros primos por debajo de"; limite
Sleep
- Output:
Números primos que contienen 123: 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Encontrados 46 números primos por debajo de 100000 Encontrados 451 números primos por debajo de 1000000
FutureBasic
include "NSLog.incl"
local fn IsPrime( n as long ) as BOOL
long i
BOOL result = YES
if ( n < 2 ) then result = NO : exit fn
for i = 2 to n + 1
if ( i * i <= n ) and ( n mod i == 0 )
result = NO : exit fn
end if
next
end fn = result
local fn PrimeWith123( limit as long )
long i, column = 1
CFStringRef numStr
NSLog( @"Prime numbers less than 100,000 which contain '123':\n" )
for i = 1 to limit
numStr = fn StringWithFormat( @"%lu", i )
if ( fn IsPrime( i ) ) and ( fn StringContainsString( numStr, @"123" ) )
NSLog( @"%-6lu\b", i )
if column == 10 then column = 0 : NSLog( @"" )
column++
end if
next
end fn
fn PrimeWith123( 100000 )
HandleEvents
- Output:
Prime numbers less than 100,000 which contain '123': 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123
Go
package main
import (
"fmt"
"rcu"
"strings"
)
func main() {
limit := 100_000
primes := rcu.Primes(limit * 10)
var results []int
for _, p := range primes {
if p < 1000 || p > 99999 {
continue
}
ps := fmt.Sprintf("%s", p)
if strings.Contains(ps, "123") {
results = append(results, p)
}
}
climit := rcu.Commatize(limit)
fmt.Printf("Primes under %s which contain '123' when expressed in decimal:\n", climit)
for i, p := range results {
fmt.Printf("%7s ", rcu.Commatize(p))
if (i+1)%10 == 0 {
fmt.Println()
}
}
fmt.Println("\n\nFound", len(results), "such primes under", climit, "\b.")
limit = 1_000_000
climit = rcu.Commatize(limit)
count := len(results)
for _, p := range primes {
if p < 100_000 {
continue
}
ps := fmt.Sprintf("%s", p)
if strings.Contains(ps, "123") {
count++
}
}
fmt.Println("\nFound", count, "such primes under", climit, "\b.")
}
- Output:
Primes under 100,000 which contain '123' when expressed in decimal: 1,123 1,231 1,237 8,123 11,239 12,301 12,323 12,329 12,343 12,347 12,373 12,377 12,379 12,391 17,123 20,123 22,123 28,123 29,123 31,123 31,231 31,237 34,123 37,123 40,123 41,231 41,233 44,123 47,123 49,123 50,123 51,239 56,123 59,123 61,231 64,123 65,123 70,123 71,233 71,237 76,123 81,233 81,239 89,123 91,237 98,123 Found 46 such primes under 100,000. Found 451 such primes under 1,000,000.
Haskell
import Data.List ( isInfixOf )
isPrime :: Int -> Bool
isPrime n
|n < 2 = False
|otherwise = null $ filter (\i -> mod n i == 0 ) [2 .. root]
where
root :: Int
root = floor $ sqrt $ fromIntegral n
condition :: Int -> Bool
condition n = isPrime n && isInfixOf "123" ( show n )
solution :: [Int]
solution = filter condition [2..99999]
- Output:
[1123,1231,1237,8123,11239,12301,12323,12329,12343,12347,12373,12377,12379,12391,17123,20123,22123,28123,29123,31123,31231,31237,34123,37123,40123,41231,41233,44123,47123,49123,50123,51239,56123,59123,61231,64123,65123,70123,71233,71237,76123,81233,81239,89123,91237,98123]
J
p:I.1 2 3 +./@E."1/ 10 #.inv p:i.p:inv 1e5 NB. primes less than 1e5 containing decimal digit sequence 1 2 3
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123
+/1 2 3 +./@E."1/ 10 #.inv p:i.p:inv 1e6 NB. count of primes less than 1e6 containing decimal digit sequence 1 2 3
451
p:inv 1e5
is 9592 -- the number of primes less than 1e5. p:i.9592
enumerates those primes (first is 2, last is 99991). 10 #.inv
converts this to the corresponding table of decimal digits (0 0 0 0 2
for the first row, 9 9 9 9 1
for the last row). 1 2 3 +./@E."1
identifies those rows containing the sequence 1 2 3
, and I.
gets the indices of those rows and, finally, p:
gets the prime numbers corresponding to those indices. Similarly, +/
counts the rows with suitable primes.
Java
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
public final class PrimeNumbersWhichContain123 {
public static void main(String[] args) {
List<Integer> primes123 = listPrimeNumbers(1_000_000)
.stream().filter( p -> Integer.toString(p).contains("123") ).toList();
List<Integer> smallPrimes123 = primes123.stream().takeWhile( i -> i < 100_000 ).toList();
System.out.println("Primes under 100,000 which contain '123':");
IntStream.range(0, smallPrimes123.size()).forEach( i ->
System.out.print(String.format("%5d%s", smallPrimes123.get(i), ( i % 10 == 9 ? "\n" : " " ))) );
System.out.println(System.lineSeparator());
System.out.println("Found " + smallPrimes123.size() + " primes less than 100,000 containing '123'.");
System.out.println();
System.out.println("Found " + primes123.size() + " primes less than 1,000,000 containing '123'.");
}
private static List<Integer> listPrimeNumbers(int limit) {
List<Integer> primes = new ArrayList<Integer>();
primes.add(2);
final int halfLimit = ( limit + 1 ) / 2;
boolean[] composite = new boolean[halfLimit];
for ( int i = 1, p = 3; i < halfLimit; p += 2, i++ ) {
if ( ! composite[i] ) {
primes.add(p);
for ( int a = i + p; a < halfLimit; a += p ) {
composite[a] = true;
}
}
}
return primes;
}
}
- Output:
Primes under 100,000 which contain '123': 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Found 46 primes less than 100,000 containing '123'. Found 451 primes less than 1,000,000 containing '123'.
jq
Works with gojq, the Go implementation of jq
For a suitable implementation of `is_prime`, see e.g. # Erdős-primes#jq.
def count(stream): reduce stream as $i (0; .+1);
def digits: tostring | explode;
# Input: an upper bound, or `infinite`
def primes_with_123:
("123"| digits) as $d123
| range(123; .; 2))
| select( (digits | index($d123)) and is_prime);
100000 | primes_with_123,
(1000000
| "\nThere are \(count(primes_with_123)) \"123\" primes less than \(.).")
- Output:
(Abbreviated)
1123 1231 1237 8123 ... 81233 81239 89123 91237 98123 There are 451 "123" primes less than 1000000.
Julia
using Primes
function containstringinbase(N, str, base, verbose = true)
arr = filter(n -> occursin(str, string(n, base=base)), primes(N))
println("\n\nFound $(length(arr)) primes < $N which contain the string $str in base $base representation.")
verbose && foreach(p -> print(rpad(p[2], 6), p[1] % 12 == 0 ? "\n" : ""), enumerate(arr))
end
containstringinbase(100_000, "123", 10)
containstringinbase(1_000_000, "123", 10, false)
containstringinbase(1_000_000_000, "123", 10, false)
- Output:
Found 46 primes < 100000 which contain the string 123 in base 10 representation. 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Found 451 primes < 1000000 which contain the string 123 in base 10 representation. Found 435002 primes < 1000000000 which contain the string 123 in base 10 representation.
Ksh
#!/bin/ksh
# Prime numbers which contain 123
# # Variables:
#
integer MAX_SHOW=100000 MAX_COUNT=1000000 primecnt=0
pattrn='123'
typeset -a parr
# # Functions:
#
# # Function _isprime(n) return 1 for prime, 0 for not prime
#
function _isprime {
typeset _n ; integer _n=$1
typeset _i ; integer _i
(( _n < 2 )) && return 0
for (( _i=2 ; _i*_i<=_n ; _i++ )); do
(( ! ( _n % _i ) )) && return 0
done
return 1
}
######
# main #
######
for ((i=2; i<MAX_COUNT; i++)); do
_isprime ${i}
if (( $? )); then
if [[ ${i} == *${pattrn}* ]]; then
((primecnt++))
(( i < MAX_SHOW )) && parr+=( ${i} )
fi
fi
done
print ${parr[*]}
print ${#parr[*]} found under $MAX_SHOW
echo ; print ${primecnt} found under $MAX_COUNT
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 1237912391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 46 found under 100000
451 found under 1000000
Mathematica /Wolfram Language
s1 = Select[Prime[Range[PrimePi[10^5]]], IntegerDigits/*(SequenceCount[#, {1, 2, 3}] &)/*GreaterThan[0]]
Length[s1]
Length[Select[Prime[Range[PrimePi[10^6]]], IntegerDigits/*(SequenceCount[#, {1, 2, 3}] &)/*GreaterThan[0]]]
- Output:
{1123, 1231, 1237, 8123, 11239, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 17123, 20123, 22123, 28123, 29123, 31123, 31231, 31237, 34123, 37123, 40123, 41231, 41233, 44123, 47123, 49123, 50123, 51239, 56123, 59123, 61231, 64123, 65123, 70123, 71233, 71237, 76123, 81233, 81239, 89123, 91237, 98123} 46 451
Nim
import sequtils, strutils
const N = 1_000_000 - 1 # Sieve of Erathostenes size.
# Sieve of Erathostenes.
var composite: array[2..N, bool]
for n in countup(3, N, 2): # We ignore the even values.
let n2 = n * n
if n2 > N: break
if not composite[n]:
for k in countup(n2, N, 2 * n):
composite[k] = true
template isPrime(n: Positive): bool = not composite[n]
iterator primes123(lim: Positive): int =
var n = 1001 # First odd value with four digits.
while n <= lim:
if n.isPrime and ($n).find("123") >= 0:
yield n
inc n, 2
let list = toSeq(primes123(100_000 - 1))
echo "Found ", list.len, " “123” primes less than 100_000:"
for i, n in list:
stdout.write ($n).align(5), if (i + 1) mod 8 == 0: '\n' else: ' '
echo '\n'
var count = 0
for _ in primes123(1_000_000): inc count
echo "Found ", count, " “123” primes less than 1_000_000."
- Output:
Found 46 “123” primes less than 100_000: 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Found 451 “123” primes less than 1_000_000.
Pascal
Free Pascal
using unit primsieve. Check only primes.
program test_123_primes;
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
uses
SysUtils,StrUtils,primsieve;
const
MaxTotLen = 1000*1000*1000;
var
PowLimit: nativeint;
TtlCnt,PrmCnt: nativeint;
p: nativeint;
begin
Writeln(' Total count Limit primes count for test');
PowLimit := 1000;
p := nextprime;// =2
TtlCnt := 0;
PrmCnt := 0;
repeat
repeat
PrmCnt +=1;
inc(TtlCnt,Ord(pos('123',IntToStr(p))>0));
p := nextprime;
until p>PowLimit;
writeln(Numb2Usa(IntToStr(TtlCnt)):12,
Numb2Usa(IntToStr(powLimit)):16,
Numb2Usa(IntToStr(PrmCnt)):16);
PowLimit *= 10;
until PowLimit> MaxTotLen;
end.
- @home N100 3,4 Ghz:
Total count Limit primes count for test 0 1,000 168 4 10,000 1,229 46 100,000 9,592 451 1,000,000 78,498 4,409 10,000,000 664,579 43,490 100,000,000 5,761,455 435,002 1,000,000,000 50,847,534 real 0m2,957s
alternative
generating numbers containing "123" and than check , if prime
program Primes_123;
{$IFDEF FPC}
{$MODE objFPC}
{$CODEALIGN proc=32,loop=1}
{$IFEND}
uses
sysutils,StrUtils,primsieve;
const
C123 = 123;
cLen123 = 3;
cPow10_3 = 1000;
cArrLenDgtCnt :array[cLen123..11] of Integer =
(1,14,185,2300,27500,320000,3650000,41000000,455000000);
const
MaxTotLen = 11;
var
PoW10: array[0..MaxTotLen] of int64;
SortArray : array of NativeInt;
SortArrayIdx : nativeint;
procedure QuickSort(var A: array of NativeInt;MaxIdx:NativeInt);
procedure QSort(L, R: Integer);
var
I, J, Tmp, Pivot: NativeInt;
begin
if R - L < 1 then exit;
I := L; J := R;
{$push}{$q-}{$r-}Pivot := A[(L + R) shr 1];{$pop}
repeat
while A[I] < Pivot do Inc(I);
while A[J] > Pivot do Dec(J);
if I <= J then begin
Tmp := A[I];
A[I] := A[J];
A[J] := Tmp;
Inc(I); Dec(J);
end;
until I > J;
QSort(L, J);
QSort(I, R);
end;
begin
QSort(0, MaxIdx-1);
end;
function Check(DgtCnt:NativeInt;var lastP:NativeInt):NativeInt;
//sort numbers and check if prime and return count
var
pArr : pNativeInt;
i,
num123,
p: NativeInt;
begin
QuickSort(SortArray,SortArrayIdx-1);
pArr := @SortArray[0];
p := Lastp;
result := 0;
num123 := 0;
For i := 0 to SortArrayIdx-1 do
begin
// no doublettes
if num123 <> pArr[i] then
begin
num123 := pArr[i];
while p < num123 do
p := NextPrime;
if p= num123 then
result += 1
end;
end;
Lastp := p;
end;
procedure AddDgtAfter(before, cnt: nativeint);
begin
if cnt=1 then
begin
SortArray[SortArrayIdx] := before;
SortArrayIdx +=1
end
else
begin
//make before odd
before += Ord(Not(Odd(before)));
repeat
SortArray[SortArrayIdx] := before;
SortArrayIdx += 1;
before += 2;
cnt -= 2;
until cnt <=0;
end;
end;
procedure Get123NumbWithDgtCnt(DgtCnt:NativeInt);
//Creating numbers with at least one "123" with DgtCnt digits
var
PowBefore: nativeint;
DgtCntBefore,DgtCntAfter,DgtBefore: nativeint;
Begin
DgtCntAfter := DgtCnt - cLen123;
PowBefore := PoW10[DgtCntAfter];
//DgtCntBefore = 0;
AddDgtAfter(C123 * PowBefore, PowBefore);
for DgtCntBefore := 1 to DgtCnt - cLen123 do
begin
DgtCntAfter -=1;
PowBefore := PoW10[DgtCntAfter];
for DgtBefore := Pow10[DgtCntBefore - 1] to Pow10[DgtCntBefore] - 1 do
AddDgtAfter((DgtBefore * cPow10_3 + C123) * PowBefore, PowBefore );
end;
end;
var
MyTime : Int64;
lastp,PowBefore: nativeint;
TtlLen,TtlCnt: nativeint;
i: nativeint;
begin
myTime := GetTickCount64;
PowBefore := 1;
for i := 0 to MaxTotLen do
begin
PoW10[i] := PowBefore;
PowBefore *= 10;
end;
//generating numbers containing "123", unordered :-(
//first 123_0,123_1,..,123_9 than 1_123,2_123,3_123
TtlLen := cLen123;
TtlCnt := 0;
setlength(SortArray,cArrLenDgtCnt[MaxTotLen]);
SortArrayIdx := 0;
lastp := 0;
writeln('Initial time ',(GetTickCount64-myTime)*0.001:8:3,' s');
myTime := GetTickCount64;
Writeln('Count of primes in decimal containing "123"');
Writeln('total count':15,'Limit':20);
repeat
Get123NumbwithDgtCnt(TtlLen);
inc(TtlCnt,Check(TtlLen,Lastp));
Writeln(Numb2USA(IntTosTr(TtlCnt)):15,
Numb2USA(IntTosTr(PoW10[TtlLen]-1)):20,
(GetTickCount64-myTime)*0.001:8:3,' s');
SortArrayIdx := 0;
Inc(TtlLen);
until TtlLen > MaxTotLen;
setlength(SortArray,0);
end.
- @home N100 3,4Ghz:
Initial time 0.558 s Count of primes in decimal containing "123" total count Limit ( runtime ) 0 999 0.000 s 4 9,999 0.000 s 46 99,999 0.000 s 451 999,999 0.001 s 4,409 9,999,999 0.009 s 43,490 99,999,999 0.103 s 435,002 999,999,999 1.193 s 4,341,024 9,999,999,999 15.068 s 43,346,024 99,999,999,999 212.527 s real 3m33,094s
Perl
#!/usr/bin/perl
use strict;
use warnings;
use ntheory qw( primes );
my @hundredthousand = grep /123/, @{ primes(1e5) };
my $million = grep /123/, @{ primes(1e6) };
print "@hundredthousand\n\nmillion count is $million\n" =~ s/.{70}\K /\n/gr;
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 million count is 451
Phix
with javascript_semantics function m123(string s) return match("123",s) end function function fn(integer n) return filter(apply(get_primes_le(n),sprint),m123) end function sequence res = fn(100_000) printf(1,"found %d < 100_000: %s\n",{length(res),join(shorten(res,"",5))}) printf(1,"found %d < 1_000_000\n",{length(fn(1_000_000))})
- Output:
found 46 < 100_000: 1123 1231 1237 8123 11239 ... 81233 81239 89123 91237 98123 found 451 < 1_000_000
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
Global column.i
Procedure prime(limite.l, mostrar.b)
column = 0
For n = 1 To limite
strn.s = Str(n)
If isPrime(n) And FindString(strn,"123") > 0:
column + 1
If mostrar:
Print(FormatNumber(n,0,"","") + " ")
If column % 8 = 0: PrintN("") : EndIf
EndIf
EndIf
Next n
EndProcedure
OpenConsole()
PrintN("Prime numbers which contain 123")
limite.l = 1e5
prime(limite, #True)
PrintN(#CRLF$ + #CRLF$ + "Found " + Str(column) + " prime numbers below " + Str(limite))
limite = 1e6
prime(limite, #False)
PrintN(#CRLF$ + "Found " + Str(column) + " prime numbers below " + Str(limite))
Input()
CloseConsole()
- Output:
Same as FreeBASIC entry.
Python
#!/usr/bin/python
def prime(limite, mostrar):
global columna
columna = 0
for n in range(limite):
strn = str(n)
if isPrime(n) and ('123' in str(n)):
columna += 1
if mostrar == True:
print(n, end=" ");
if columna % 8 == 0:
print('')
return columna
if __name__ == "__main__":
print("Números primos que contienen 123:")
limite = 100000
prime(limite, True)
print("\n\nEncontrados ", columna, " números primos por debajo de", limite)
limite = 1000000
prime(limite, False)
print("\n\nEncontrados ", columna, " números primos por debajo de", limite)
- Output:
Igual que la entrada de FreeBASIC.
Quackery
eratosthenes
and isprime
are defined at Sieve of Eratosthenes#Quackery.
100000 eratosthenes
[ false swap
[ dup 122 > while
dup 1000 mod
123 = iff
[ dip not ]
done
10 / again ]
drop ] is contains123 ( n --> b )
[]
100000 times
[ i^ isprime if
[ i^ contains123 if
[ i^ join ] ] ]
[] swap witheach
[ number$ nested join ]
48 wrap$
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123
Raku
my @p123 = ^∞ .grep: { (.contains: 123) && .is-prime };
put display @p123[^(@p123.first: * > 1e5, :k)];
put "\nCount up to 1e6: ", ~ +@p123[^(@p123.first: * > 1e6, :k)];
sub display ($list, :$cols = 10, :$fmt = '%6d', :$title = "{+$list} matching:\n" ) {
cache $list;
$title ~ $list.batch($cols)».fmt($fmt).join: "\n"
}
- Output:
46 matching: 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Count up to 1e6: 451
REXX
Modules: How to use
Modules: Source code
Procedure Primes in Sequences sieves the needed primes.
-- 26 Mar 2025
include Settings
numeric digits 10
arg xx
if xx = '' then
xx = 1e5
say 'PRIME NUMBERS WHICH CONTAIN 123'
say version
say
call GetPrimes xx
call ShowPrimes
exit
GetPrimes:
call Time('r')
arg xx
say 'Analysis for primes up to' xx 'follows'
say
say 'Get primes...'
call Primes xx
say prim.0 'primes found'
say Format(Time('e'),,3) 'seconds'; say
return
ShowPrimes:
call Time('r')
say 'Show primes...'
n = 0; a = prim.0; p = prim.a
do i = 1 to prim.0
if Pos('123',prim.i) = 0 then
iterate
n = n+1
if p > 1e5 then
iterate
call Charout ,Right(prim.i,7)
if n//10 = 0 then
say
end
say
say n 'such primes found'
say Format(Time('e'),,3) 'seconds'; say
return
include Sequences
include Functions
include Abend
- Output:
PRIME NUMBERS WHICH CONTAIN 123 REXX-Regina_3.9.6(MT) 5.00 29 Apr 2024 Analysis for primes up to 1E5 follows Get primes... 9592 primes found 0.020 seconds Show primes... 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 46 such primes found 0.002 seconds Analysis for primes up to 1E6 follows Get primes... 78498 primes found 0.267 seconds Show primes... 451 such primes found 0.017 seconds Analysis for primes up to 1E7 follows Get primes... 664579 primes found 3.112 seconds Show primes... 4409 such primes found 0.144 seconds Analysis for primes up to 1E8 follows Get primes... 5761455 primes found 38.719 seconds Show primes... 43490 such primes found 2.187 seconds
Ring
load "stdlib.ring"
row = 0
see "working..." + nl
see "Prime numbers which contain 123 are:" + nl
for n = 1 to 100000
strn = string(n)
ind = substr(strn,"123")
if isprime(n) and ind > 0
see "" + n + " "
row++
if row%5 = 0
see nl
ok
ok
next
see nl + "Found " + row + " numbers" + nl
see "done..." + nl
- Output:
working... Prime numbers which contain 123 are: 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Found 46 numbers done...
RPL
Brute force
≪ ALOG → max
≪ { } 1123
WHILE DUP max < REPEAT
NEXTPRIME
IF DUP →STR "123" POS THEN SWAP OVER + SWAP END
END NIP
≫ ≫ 'TASK’ STO
- Output:
1: { 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 }
Runs in 12 minutes 45 seconds on a HP-50g
Lexicographic approach
RPL code | Comment |
---|---|
≪
3 - DUP ALOG 1 - { } → ndigits maxleft results
≪ 0
DO
DUP DUP "" IFTE
ndigits OVER SIZE - ALOG 1 +
DUP 2 x 3 - FOR j
DUP "123" + j →STR TAIL + STR→
IF DUP ISPRIME? THEN 'results' STO+ ELSE DROP END
2 STEP
DROP 1 +
UNTIL DUP maxleft > END
DROP results
≫ ≫ 'PR123N’ STO
|
PR123N ( n_digits → { primes_with_123 } )
n_digits -= 3 ; maxleft = 10^n_digits - 1
leftval = 0
loop
left = leftval == 0 ? "" ; leftval
tmp = 10^(n_digits - length(leftval)) + 1
for j = tmp to (tmp*2 - 3) step 2
n = left + "123" + j[2..]
add n to results if prime
next j
leftval++
end loop
display results (unsorted)
|
4 PR123N 5 PR123N + SORT
Runs in 22 seconds on a HP-50g (35 times faster than brute force) - same results as above. Finding the 451 primes under one million takes 4 minutes 30 seconds.
Ruby
require 'prime'
RE = /123/
puts Prime.each(100_000).select {|prime| RE.match? prime.to_s}.join(" "), ""
puts "#{Prime.each(1_000_000).count {|prime| RE.match? prime.to_s} } 123-primes below 1 million."
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 451 123-primes below 1 million.
Sidef
func numbers_with_subdigits(upto, base = 10, s = 123.digits(base)) {
Enumerator({|callback|
for k in (0 .. base**(upto.len(base) - s.len)) {
var d = k.digits(base)
for i in (0 .. d.len) {
var n = d.clone.insert(i, s...).digits2num(base)
callback(n) if (n <= upto)
}
var z = d.clone.insert(d.len, s...)
loop {
var n = z.insert(d.len, 0).digits2num(base)
(n <= upto) ? callback(n) : break
}
}
})
}
say "Decimal primes under 100,000 which contain '123':"
numbers_with_subdigits(1e5).grep { .is_prime }.sort.each_slice(10, {|*a|
say a.map { '%6s' % _ }.join(' ')
})
say ''
for n in (4..8) {
var count = numbers_with_subdigits(10**n).grep { .is_prime }.len
say "Found #{'%6s' % count.commify} such primes < 10^#{n}"
}
- Output:
Decimal primes under 100,000 which contain '123': 1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 Found 4 such primes < 10^4 Found 46 such primes < 10^5 Found 451 such primes < 10^6 Found 4,412 such primes < 10^7 Found 43,548 such primes < 10^8
Wren
The only number under 1,000 which can possibly satisfy the task description is 123 and that's clearly divisible by 3 and hence composite.
import "./math" for Int
import "./fmt" for Fmt
var limit = 1e5
var primes = Int.primeSieve(limit * 10).where { |p| p > 999 }
var results = primes.where { |p| p < limit && p.toString.contains("123") }.toList
Fmt.print("Primes under $,d which contain '123' when expressed in decimal:", limit)
Fmt.tprint("$,7d", results, 10)
Fmt.print("\nFound $,d such primes under $,d.", results.count, limit)
limit = 1e6
var count = primes.count { |p| p.toString.contains("123") }
Fmt.print("\nFound $,d such primes under $,d.", count, limit)
- Output:
Primes under 100,000 which contain '123' when expressed in decimal: 1,123 1,231 1,237 8,123 11,239 12,301 12,323 12,329 12,343 12,347 12,373 12,377 12,379 12,391 17,123 20,123 22,123 28,123 29,123 31,123 31,231 31,237 34,123 37,123 40,123 41,231 41,233 44,123 47,123 49,123 50,123 51,239 56,123 59,123 61,231 64,123 65,123 70,123 71,233 71,237 76,123 81,233 81,239 89,123 91,237 98,123 Found 46 such primes under 100,000. Found 451 such primes under 1,000,000.
XPL0
func IsPrime(N); \Return 'true' if N is a prime number
int N, I;
[if N <= 1 then return false;
for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true;
];
func Has123(N); \Return 'true' if N contains sequential digits 1 2 3
int N, C, D;
[C:= 3;
repeat N:= N/10;
D:= rem(0);
if D = C then
[C:= C-1;
if C = 0 then return true;
]
else [C:= 3;
if D = C then C:= 2;
];
until N=0;
return false;
];
int N, Count;
[Count:= 0;
for N:= 123 to 1_000_000-1 do
[if Has123(N) then if IsPrime(N) then
[Count:= Count+1;
if N < 100_000 then
[IntOut(0, N);
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
];
];
if N = 100_000 then
[CrLf(0); IntOut(0, Count); Text(0, " ^"123^" primes found below 100,000.")];
];
CrLf(0); IntOut(0, Count); Text(0, " ^"123^" primes found below 1,000,000.");
]
- Output:
1123 1231 1237 8123 11239 12301 12323 12329 12343 12347 12373 12377 12379 12391 17123 20123 22123 28123 29123 31123 31231 31237 34123 37123 40123 41231 41233 44123 47123 49123 50123 51239 56123 59123 61231 64123 65123 70123 71233 71237 76123 81233 81239 89123 91237 98123 46 "123" primes found below 100,000. 451 "123" primes found below 1,000,000.
Yabasic
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 prime(limite, mostrar)
local n
n = 0
columna = 0
for n = 1 to limite
strn$ = str$(n)
if isPrime(n) and instr(strn$,"123") > 0 then
columna = columna + 1
if mostrar then
print " ", n using "#####", " ";
if mod(columna, 8) = 0 then print : fi
endif
endif
next n
end sub
print "N£meros primos que contienen 123:\n"
limite = 1e5
prime(limite, true)
print "\n\nEncontrados ", columna, " n£meros primos por debajo de ", limite
limite = 1e6
prime(limite, false)
print "\n\nEncontrados ", columna, " n£meros primos por debajo de ", limite
end
- Output:
Igual que la entrada de FreeBASIC.
- Draft Programming Tasks
- Prime Numbers
- 11l
- ALGOL 68
- ALGOL 68-primes
- Arturo
- AWK
- BASIC256
- C++
- Clojure
- CLU
- Delphi
- SysUtils,StdCtrls
- EasyLang
- F Sharp
- FreeBASIC
- FutureBasic
- Go
- Go-rcu
- Haskell
- J
- Java
- Jq
- Julia
- Ksh
- Mathematica
- Wolfram Language
- Nim
- Pascal
- Free Pascal
- Perl
- Ntheory
- Phix
- PureBasic
- Python
- Quackery
- Raku
- REXX
- Ring
- RPL
- Ruby
- Sidef
- Wren
- Wren-math
- Wren-fmt
- XPL0
- Yabasic