Prime numbers which contain 123: Difference between revisions
m (→{{header|Factor}}: they can't end in 5...) |
|||
| Line 67: | Line 67: | ||
<< |
<< |
||
CONSTANT: d { 0 1 2 3 4 5 6 7 8 9 } ! digits that can be anywhere |
CONSTANT: d { 0 1 2 3 4 5 6 7 8 9 } ! digits that can be anywhere |
||
CONSTANT: e { 1 3 |
CONSTANT: e { 1 3 7 9 } ! digits that can be at the end |
||
>> |
>> |
||
| Line 111: | Line 111: | ||
Found 43,548 such primes under 100,000,000. |
Found 43,548 such primes under 100,000,000. |
||
Found 435,853 such primes under 1,000,000,000. |
Found 435,853 such primes under 1,000,000,000. |
||
Running time: 23. |
Running time: 23.20984574 seconds |
||
</pre> |
</pre> |
||
Revision as of 10:43, 13 July 2021
- 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.
ALGOL 68
<lang algol68>BEGIN # find primes whose decimal representation contains 123 #
INT max prime = 1 000 000;
# sieve the primes to max prime #
[ 1 : max prime ]BOOL prime;
prime[ 1 ] := FALSE; prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD FI
OD;
# 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</lang>
- 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
Factor
<lang factor>USING: assocs assocs.extras formatting grouping io kernel literals math math.functions math.functions.integer-logs math.primes math.statistics sequences sequences.extras sequences.product sorting tools.memory.private tools.time ;
<< CONSTANT: d { 0 1 2 3 4 5 6 7 8 9 } ! digits that can be anywhere CONSTANT: e { 1 3 7 9 } ! digits that can be at the end >>
CONSTANT: digits {
${ { 1 } { 2 } { 3 } d d d d d e }
${ d { 1 } { 2 } { 3 } d d d d e }
${ d d { 1 } { 2 } { 3 } d d d e }
${ d d d { 1 } { 2 } { 3 } d d e }
${ d d d d { 1 } { 2 } { 3 } d e }
${ d d d d d { 1 } { 2 } { 3 } e }
${ d d d d d d { 1 } { 2 } { 3 } }
}
- candidates ( -- seq )
digits [ <product-sequence> ] map-concat [ <reversed> 0 [ 10^ * + ] reduce-index ] map ;
- 123primes ( -- assoc )
candidates [ prime? ] filter [ integer-log10 1 + ] collect-by >alist natural-sort ;
[
"Decimal primes under 100,000 which contain '123':" print 123primes dup [ 4 of ] [ 5 of append ] bi natural-sort 10 group [ [ commas "%8s" printf ] each nl ] each nl [ [ 10^ commas ] [ length ] bi* ] assoc-map unzip cum-sum [ commas ] map zip assoc-invert [ "Found %7s such primes under %s.\n" printf ] assoc-each
] time</lang>
- Output:
Decimal primes under 100,000 which contain '123': 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 4 such primes under 10,000. Found 46 such primes under 100,000. Found 451 such primes under 1,000,000. Found 4,412 such primes under 10,000,000. Found 43,548 such primes under 100,000,000. Found 435,853 such primes under 1,000,000,000. Running time: 23.20984574 seconds
FreeBASIC
<lang 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 </lang>
- 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
Go
<lang 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.")
}</lang>
- 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.
Julia
<lang julia>using Primes
function containstringinbase(N, str, base)
arr = filter(n -> occursin(str, string(n, base=base)), primes(N))
println("Found $(length(arr)) primes < $N which contain the string $str in base $base representation:")
foreach(p -> print(rpad(p[2], 6), p[1] % 12 == 0 ? "\n" : ""), enumerate(arr))
end
containstringinbase(100_000, "123", 10)
</lang>
- 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
Nim
<lang 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."</lang>
- 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.
Phix
with javascript_semantics function cs(string n, s) return match(s,n) end function function fn(integer n) return filter(apply(get_primes_le(n),sprint),cs,"123") end function sequence res = fn(100_000) printf(1,"found %d < 100_000: %s\n",{length(res),join(shorten(res,"",5))}) res = fn(1_000_000) printf(1,"found %d < 1_000_000\n",{length(res)})
- Output:
found 46 < 100_000: 1123 1231 1237 8123 11239 ... 81233 81239 89123 91237 98123 found 451 < 1_000_000
Python
<lang 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)
</lang>
- Output:
Igual que la entrada de FreeBASIC.
Raku
<lang perl6>my @p123 = ^∞ .grep: { .is-prime && .contains: 123 };
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"
}</lang>
- 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
This REXX versions allows the user to specify (on the command line) the high limit for the primes to be searched,
the number of columns to be shown, and the decimal string that the primes must contain. A negative number for
the number of columns suppresses the list of primes, but shows the total number of primes found.
<lang rexx>/*REXX program finds & displays primes (in decimal) that contain the decimal digits 123.*/
parse arg hi cols str . /*obtain optional argument from the CL.*/
if hi== | hi=="," then hi= 100000 /*Not specified? Then use the default.*/
if cols== | cols=="," then cols= 10 /* " " " " " " */
if str== | str=="," then str= 123 /* " " " " " " */
call genP /*build array of semaphores for primes.*/
w= 10 /*width of a number in any column. */
title= ' primes N (in decimal) that contain the decimal digits string ' str ,
" (in order), where N < " commas(hi)
if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') found= 0; idx= 1 /*initialize # of primes found; IDX. */ $= /*list of primes that contain a string.*/
do j=1 for # /*search list of primes that have a str*/
if pos(str, @.j)==0 then iterate /*does this decimal prime contain "123"*/ /* ◄■■■■■■■ the filter.*/
found= found + 1 /*bump the number of primes found. */
if cols<0 then iterate /*Build the list (to be shown later)? */
c= commas(@.j) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add a prime ──► $ list, allow big #*/
if found//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' commas(found) title exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " semaphores. */
#=5; sq.#= @.# **2 /*number of primes so far; prime². */
do j=@.#+2 by 2 to hi-1 /*find odd primes from here on. */
parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; sq.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return</lang>
- output when using the default inputs:
index │ primes N (in decimal) that contain the decimal digits string 123 (in order), where N < 100,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 1,123 1,231 1,237 8,123 11,239 12,301 12,323 12,329 12,343 12,347 11 │ 12,373 12,377 12,379 12,391 17,123 20,123 22,123 28,123 29,123 31,123 21 │ 31,231 31,237 34,123 37,123 40,123 41,231 41,233 44,123 47,123 49,123 31 │ 50,123 51,239 56,123 59,123 61,231 64,123 65,123 70,123 71,233 71,237 41 │ 76,123 81,233 81,239 89,123 91,237 98,123 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 46 primes N (in decimal) that contain the decimal digits string 123 (in order), where N < 100,000
- output when using the default inputs: 1000000 -1
Found 451 primes N (in decimal) that contain the decimal digits string 123 (in order), where N < 1,000,000
Ring
<lang 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 </lang>
- 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...
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. <lang ecmascript>import "/math" for Int import "/fmt" for Fmt import "/seq" for Lst
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) for (chunk in Lst.chunks(results, 10)) Fmt.print("$,7d", chunk) 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)</lang>
- 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.
Yabasic
<lang 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 </lang>
- Output:
Igual que la entrada de FreeBASIC.