Primes which contain only one odd digit
- Task
Show on this page those primes under 1,000 which when expressed in decimal contains only one odd digit.
- Stretch goal
Show on this page only the count of those primes under 1,000,000 which when expressed in decimal contains only one odd digit.
ALGOL 68
<lang algol68>BEGIN # find primes whose decimal representation contains only one odd digit #
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; # show a count of primes # PROC show total = ( INT count, INT limit, STRING name )VOID: print( ( newline, "Found ", whole( count, 0 ), " ", name, " primes upto ", whole( limit, 0 ), newline ) ); # find the appropriate primes # # 2 is the only even prime, so the final digit must be odd for primes > 2 # # so we only need to check that the digits other than the last are all even # INT show max = 1 000; INT p1odd count := 0; FOR n FROM 3 TO UPB prime DO IF prime[ n ] THEN BOOL p1odd := TRUE; INT v := n OVER 10; WHILE v > 0 AND ( p1odd := NOT ODD v ) DO v OVERAB 10 OD; IF p1odd THEN # the prime has only 1 odd digit # p1odd count +:= 1; IF n <= show max THEN print( ( whole( n, -5 ) ) ); IF p1odd count MOD 12 = 0 THEN print( ( newline ) ) FI FI FI FI; IF n = show max THEN print( ( newline ) ); show total( p1odd count, show max, "single-odd-digit" ) FI OD; show total( p1odd count, UPB prime, "single-odd-digit" )
END</lang>
- Output:
3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887 Found 45 single-odd-digit primes upto 1000 Found 2560 single-odd-digit primes upto 1000000
F#
<lang fsharp> // Primes which contain only one odd number. Nigel Galloway: July 28th., 2021 let rec fN g=function 2->false |n when g=0->n=1 |n->fN (g/10) (n+g%2) primes32()|>Seq.takeWhile((>)1000)|>Seq.filter(fun g->fN g 0)|>Seq.iter(printf "%d "); printfn "" </lang>
- Output:
3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887
Go
<lang go>package main
import (
"fmt" "rcu"
)
func allButOneEven(prime int) bool {
digits := rcu.Digits(prime, 10) digits = digits[:len(digits)-1] allEven := true for _, d := range digits { if d&1 == 1 { allEven = false break } } return allEven
}
func main() {
const ( LIMIT = 999 LIMIT2 = 999999 MAX_DIGITS = 3 ) primes := rcu.Primes(LIMIT) var results []int for _, prime := range primes[1:] { if allButOneEven(prime) { results = append(results, prime) } } fmt.Println("Primes under", rcu.Commatize(LIMIT+1), "which contain only one odd digit:") for i, p := range results { fmt.Printf("%*s ", MAX_DIGITS, rcu.Commatize(p)) if (i+1)%9 == 0 { fmt.Println() } } fmt.Println("\nFound", len(results), "such primes.")
primes = rcu.Primes(LIMIT2) count := 0 for _, prime := range primes[1:] { if allButOneEven(prime) { count = count + 1 } } cs := rcu.Commatize(count) ls := rcu.Commatize(LIMIT2 + 1) fmt.Println("\nThere are", cs, "primes under", ls, "which contain only one odd digit.")
}</lang>
- Output:
Primes under 1,000 which contain only one odd digit: 3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887 Found 45 such primes. There are 2,560 primes under 1,000,000 which contain only one odd digit.
Julia
If only one digit of a prime is odd, then that odd digit is the ones place digit. We don't actually need to check for an odd first digit once we exclude 2. <lang julia>using Primes
function isoneoddprime(n, base = 10)
d = digits(n ÷ base, base = base) return n != 2 && all(iseven, d)
end
found = filter(isoneoddprime, primes(1000)) println("Found $(length(found)) primes with one odd digit in base 10:") foreach(p -> print(rpad(last(p), 5), first(p) % 9 == 0 ? "\n" : ""), enumerate(found))
</lang>
- Output:
Found 45 primes with one odd digit in base 10: 3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887
Nim
<lang Nim>import sequtils, strutils
func isPrime(n: Positive): bool =
if n == 1: return false if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false inc d, 2 if n mod d == 0: return false inc d, 4 result = true
func hasLastDigitOdd(n: Natural): bool =
var n = n n = n div 10 while n != 0: if (n mod 10 and 1) != 0: return false n = n div 10 result = true
iterator primesOneOdd(lim: Positive): int =
var n = 1 while n <= lim: if n.hasLastDigitOdd and n.isPrime: yield n inc n, 2
let list = toSeq(primesOneOdd(1000))
echo "Found $# primes with only one odd digit below 1000:".format(list.len)
for i, n in list:
stdout.write ($n).align(3), if (i + 1) mod 9 == 0: '\n' else: ' '
var count = 0 for _ in primesOneOdd(100_000_000):
inc count
echo "\nFound $# primes with only one odd digit below 1_000_000.".format(count)</lang>
- Output:
Found 45 primes with only one odd digit below 1000: 3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887 Found 2560 primes with only one odd digit below 1_000_000.
Raku
<lang perl6>put display ^1000 .grep: { ($_ % 2) && .is-prime && (.comb[^(*-1)].all %% 2) }
sub display ($list, :$cols = 10, :$fmt = '%6d', :$title = "{+$list} matching:\n" ) {
cache $list; $title ~ $list.batch($cols)».fmt($fmt).join: "\n"
}</lang>
- Output:
45 matching: 3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887
REXX
<lang rexx>/*REXX pgm finds & displays primes (base ten) that contain only one odd digit (< 1,000).*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 1000 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */ title= ' primes N (in base ten) that only contain one odd digit, 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=2 for #-1; p= @.j; L= length(p) /*find primes with leading/trailing dig*/ z= 0 do k=L by -1 for L if verify(substr(p, k, 1), 13579, 'M')>0 then do; z= z+1; if z>1 then iterate j /* ◄■■■■■■■ the filter.*/ end end /*k*/ 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. */
#=5; sq.#= @.# **2 /*number of primes so far; prime square*/ 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 /*bump # of Ps; assign next P; P square*/ end /*j*/; return</lang>
- output when using the default inputs:
index │ primes N (in base ten) that only contain one odd digit, where N < 1,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 3 5 7 23 29 41 43 47 61 67 11 │ 83 89 223 227 229 241 263 269 281 283 21 │ 401 409 421 443 449 461 463 467 487 601 31 │ 607 641 643 647 661 683 809 821 823 827 41 │ 829 863 881 883 887 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 45 primes N (in base ten) that only contain one odd digit, where N < 1,000
- output when using the inputs of: 1000000 -1
Found 2,560 primes N (in base ten) that only contain one odd digit, where N < 1,000,000
Ring
<lang ring> load "stdlib.ring" see "working..." + nl see "Primes which contain only one odd number:" + nl row = 0
for n = 1 to 1000
odd = 0 str = string(n) for m = 1 to len(str) if number(str[m])%2 = 1 odd++ ok next if odd = 1 and isprime(n) see "" + n + " " row++ if row%5 = 0 see nl ok ok
next
see "Found " + row + " prime numbers" + nl see "done..." + nl </lang>
- Output:
working... Primes which contain only one odd number: 3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887 Found 45 prime numbers done...
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt import "/seq" for Lst
var limit = 999 var maxDigits = 3 var primes = Int.primeSieve(limit) var results = [] for (prime in primes.skip(1)) {
if (Int.digits(prime)[0...-1].all { |d| d & 1 == 0 }) results.add(prime)
} Fmt.print("Primes under $,d which contain only one odd digit:", limit + 1) for (chunk in Lst.chunks(results, 9)) Fmt.print("$,%(maxDigits)d", chunk) System.print("\nFound %(results.count) such primes.")
limit = 999999 primes = Int.primeSieve(limit) var count = 0 for (prime in primes.skip(1)) {
if (Int.digits(prime)[0...-1].all { |d| d & 1 == 0 }) count = count + 1
} Fmt.print("\nThere are $,d primes under $,d which contain only one odd digit.", count, limit + 1)</lang>
- Output:
Primes under 1,000 which contain only one odd digit: 3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887 Found 45 such primes. There are 2,560 primes under 1,000,000 which contain only one odd digit.
XPL0
<lang 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; ];
int Count, N, Hun, Ten, One; [Count:= 0; for Hun:= 0 to 4 do
for Ten:= 0 to 4 do for One:= 0 to 4 do [N:= Hun*200 + Ten*20 + One*2 + 1; if IsPrime(N) then [IntOut(0, N); Count:= Count+1; if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\); ]; ];
CrLf(0); IntOut(0, Count); Text(0, " such numbers found. "); ]</lang>
- Output:
3 5 7 23 29 41 43 47 61 67 83 89 223 227 229 241 263 269 281 283 401 409 421 443 449 461 463 467 487 601 607 641 643 647 661 683 809 821 823 827 829 863 881 883 887 45 such numbers found.