Prime numbers which contain 123: Difference between revisions
m (added prime numbers to the task's category.) |
(Added Algol 68) |
||
| Line 8: | Line 8: | ||
As above, but only show the <u>count</u> of those primes '''n''' that contain the (above) string, where '''n < 1,000,000'''. |
As above, but only show the <u>count</u> of those primes '''n''' that contain the (above) string, where '''n < 1,000,000'''. |
||
<br><br> |
<br><br> |
||
=={{header|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> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
Revision as of 17:00, 12 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
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
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.