I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Ascending primes

From Rosetta Code
Task
Ascending primes
You are encouraged to solve this task according to the task description, using any language you may know.

Generate and show all primes with strictly ascending decimal digits.

Aside: Try solving without peeking at existing solutions. I had a weird idea for generating a prime sieve faster, which needless to say didn't pan out. The solution may be p(r)etty trivial but generating them quickly is at least mildly interesting. Tip: filtering all 7,027,260 primes below 123,456,789 probably won't kill you, but there is at least one significantly better and much faster way, needing a mere 511 odd/prime tests.


See also


Related


ALGOL 68[edit]

Uses Pete's hint to enumerate the 512 possible numbers.
The numbers are generated in order of the first digit, so we have to sort them. As there are only 512 possible numbers to consider, it doesn't attempt the optimisation that the final digit can't be 4, 6 or 8 and can only be 2 or 5 if it is the only digit (also, I always forget that can't be even thing...).

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32
Library: ALGOL 68-rows
BEGIN # find all primes with strictly increasing digits                      #
PR read "primes.incl.a68" PR # include prime utilities #
PR read "rows.incl.a68" PR # include array utilities #
[ 1 : 512 ]INT primes; # there will be at most 512 (2^9) primes #
INT p count := 0; # number of primes found so far #
FOR d1 FROM 0 TO 1 DO
INT n1 = d1;
FOR d2 FROM 0 TO 1 DO
INT n2 = IF d2 = 1 THEN ( n1 * 10 ) + 2 ELSE n1 FI;
FOR d3 FROM 0 TO 1 DO
INT n3 = IF d3 = 1 THEN ( n2 * 10 ) + 3 ELSE n2 FI;
FOR d4 FROM 0 TO 1 DO
INT n4 = IF d4 = 1 THEN ( n3 * 10 ) + 4 ELSE n3 FI;
FOR d5 FROM 0 TO 1 DO
INT n5 = IF d5 = 1 THEN ( n4 * 10 ) + 5 ELSE n4 FI;
FOR d6 FROM 0 TO 1 DO
INT n6 = IF d6 = 1 THEN ( n5 * 10 ) + 6 ELSE n5 FI;
FOR d7 FROM 0 TO 1 DO
INT n7 = IF d7 = 1 THEN ( n6 * 10 ) + 7 ELSE n6 FI;
FOR d8 FROM 0 TO 1 DO
INT n8 = IF d8 = 1 THEN ( n7 * 10 ) + 8 ELSE n7 FI;
FOR d9 FROM 0 TO 1 DO
INT n9 = IF d9 = 1 THEN ( n8 * 10 ) + 9 ELSE n8 FI;
IF n9 > 0 THEN
IF is probably prime( n9 ) THEN
# have a prime with strictly ascending digits #
primes[ p count +:= 1 ] := n9
FI
FI
OD
OD
OD
OD
OD
OD
OD
OD
OD;
QUICKSORT primes FROMELEMENT 1 TOELEMENT p count; # sort the primes #
FOR i TO p count DO # display the primes #
print( ( " ", whole( primes[ i ], -8 ) ) );
IF i MOD 10 = 0 THEN print( ( newline ) ) FI
OD
END
Output:
         2         3         5         7        13        17        19        23        29        37
        47        59        67        79        89       127       137       139       149       157
       167       179       239       257       269       347       349       359       367       379
       389       457       467       479       569      1237      1249      1259      1279      1289
      1367      1459      1489      1567      1579      1789      2347      2357      2389      2459
      2467      2579      2689      2789      3457      3467      3469      4567      4679      4789
      5689     12347     12379     12457     12479     12569     12589     12689     13457     13469
     13567     13679     13789     15679     23459     23567     23689     23789     25679     34589
     34679    123457    123479    124567    124679    125789    134789    145679    234589    235679
    235789    245789    345679    345689   1234789   1235789   1245689   1456789  12356789  23456789

Arturo[edit]

ascending?: function [x][
initial: digits x
and? [equal? sort initial initial][equal? size initial size unique initial]
]
 
candidates: select (1..1456789) ++ [
12345678, 12345679, 12345689, 12345789, 12346789,
12356789, 12456789, 13456789, 23456789, 123456789
] => prime?
 
ascendingNums: select candidates => ascending?
 
loop split.every:10 ascendingNums 'nums [
print map nums 'num -> pad to :string num 10
]
Output:
         2          3          5          7         13         17         19         23         29         37 
        47         59         67         79         89        127        137        139        149        157 
       167        179        239        257        269        347        349        359        367        379 
       389        457        467        479        569       1237       1249       1259       1279       1289 
      1367       1459       1489       1567       1579       1789       2347       2357       2389       2459 
      2467       2579       2689       2789       3457       3467       3469       4567       4679       4789 
      5689      12347      12379      12457      12479      12569      12589      12689      13457      13469 
     13567      13679      13789      15679      23459      23567      23689      23789      25679      34589 
     34679     123457     123479     124567     124679     125789     134789     145679     234589     235679 
    235789     245789     345679     345689    1234789    1235789    1245689    1456789   12356789   23456789

AWK[edit]

 
# syntax: GAWK -f ASCENDING_PRIMES.AWK
BEGIN {
start = 1
stop = 23456789
for (i=start; i<=stop; i++) {
if (is_prime(i)) {
primes++
leng = length(i)
flag = 1
for (j=1; j<leng; j++) {
if (substr(i,j,1) >= substr(i,j+1,1)) {
flag = 0
break
}
}
if (flag) {
printf("%9d%1s",i,++count%10?"":"\n")
}
}
}
printf("\n%d-%d: %d primes, %d ascending primes\n",start,stop,primes,count)
exit(0)
}
function is_prime(n, d) {
d = 5
if (n < 2) { return(0) }
if (n % 2 == 0) { return(n == 2) }
if (n % 3 == 0) { return(n == 3) }
while (d*d <= n) {
if (n % d == 0) { return(0) }
d += 2
if (n % d == 0) { return(0) }
d += 4
}
return(1)
}
 
Output:
        2         3         5         7        13        17        19        23        29        37
       47        59        67        79        89       127       137       139       149       157
      167       179       239       257       269       347       349       359       367       379
      389       457       467       479       569      1237      1249      1259      1279      1289
     1367      1459      1489      1567      1579      1789      2347      2357      2389      2459
     2467      2579      2689      2789      3457      3467      3469      4567      4679      4789
     5689     12347     12379     12457     12479     12569     12589     12689     13457     13469
    13567     13679     13789     15679     23459     23567     23689     23789     25679     34589
    34679    123457    123479    124567    124679    125789    134789    145679    234589    235679
   235789    245789    345679    345689   1234789   1235789   1245689   1456789  12356789  23456789

1-23456789: 1475171 primes, 100 ascending primes

F#[edit]

This task uses Extensible Prime Generator (F#)

 
// Ascending primes. Nigel Galloway: April 19th., 2022
[2;3;5;7]::List.unfold(fun(n,i)->match n with []->None |_->let n=n|>List.map(fun(n,g)->[for n in n.. -1..1->(n-1,i*n+g)])|>List.concat in Some(n|>List.choose(fun(_,n)->if isPrime n then Some n else None),(n|>List.filter(fst>>(<)0),i*10)))([(2,3);(6,7);(8,9)],10)
|>List.concat|>List.sort|>List.iter(printf "%d "); printfn ""
 
Output:
2 3 5 7 13 17 19 23 29 37 47 59 67 79 89 127 137 139 149 157 167 179 239 257 269 347 349 359 367 379 389 457 467 479 569 1237 1249 1259 1279 1289 1367 1459 1489 1567 1579 1789 2347 2357 2389 2459 2467 2579 2689 2789 3457 3467 3469 4567 4679 4789 5689 12347 12379 12457 12479 12569 12589 12689 13457 13469 13567 13679 13789 15679 23459 23567 23689 23789 25679 34589 34679 123457 123479 124567 124679 125789 134789 145679 234589 235679 235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789

Factor[edit]

The approach taken is to check the members of the powerset of [1..9] (of which there are only 512 if you include the empty set) for primality.

Works with: Factor version 0.99 2021-06-02
USING: grouping math math.combinatorics math.functions
math.primes math.ranges prettyprint sequences sequences.extras ;
 
9 [1,b] all-subsets [ reverse 0 [ 10^ * + ] reduce-index ]
[ prime? ] map-filter 10 group simple-table.
Output:
2      3      5      7      13      17      19      23      29       37
47     59     67     79     89      127     137     139     149      157
167    179    239    257    269     347     349     359     367      379
389    457    467    479    569     1237    1249    1259    1279     1289
1367   1459   1489   1567   1579    1789    2347    2357    2389     2459
2467   2579   2689   2789   3457    3467    3469    4567    4679     4789
5689   12347  12379  12457  12479   12569   12589   12689   13457    13469
13567  13679  13789  15679  23459   23567   23689   23789   25679    34589
34679  123457 123479 124567 124679  125789  134789  145679  234589   235679
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789

Go[edit]

Translation of: Wren
Library: Go-rcu

Using a generator.

package main
 
import (
"fmt"
"rcu"
"sort"
)
 
var ascPrimesSet = make(map[int]bool) // avoids duplicates
 
func generate(first, cand, digits int) {
if digits == 0 {
if rcu.IsPrime(cand) {
ascPrimesSet[cand] = true
}
return
}
for i := first; i < 10; i++ {
next := cand*10 + i
generate(i+1, next, digits-1)
}
}
 
func main() {
for digits := 1; digits < 10; digits++ {
generate(1, 0, digits)
}
le := len(ascPrimesSet)
ascPrimes := make([]int, le)
i := 0
for k := range ascPrimesSet {
ascPrimes[i] = k
i++
}
sort.Ints(ascPrimes)
fmt.Println("There are", le, "ascending primes, namely:")
for i := 0; i < le; i++ {
fmt.Printf("%8d ", ascPrimes[i])
if (i+1)%10 == 0 {
fmt.Println()
}
}
}
Output:
There are 100 ascending primes, namely:
       2        3        5        7       13       17       19       23       29       37 
      47       59       67       79       89      127      137      139      149      157 
     167      179      239      257      269      347      349      359      367      379 
     389      457      467      479      569     1237     1249     1259     1279     1289 
    1367     1459     1489     1567     1579     1789     2347     2357     2389     2459 
    2467     2579     2689     2789     3457     3467     3469     4567     4679     4789 
    5689    12347    12379    12457    12479    12569    12589    12689    13457    13469 
   13567    13679    13789    15679    23459    23567    23689    23789    25679    34589 
   34679   123457   123479   124567   124679   125789   134789   145679   234589   235679 
  235789   245789   345679   345689  1234789  1235789  1245689  1456789 12356789 23456789 

J[edit]

Compare with Descending primes.

Live link.

   extend=: {{ y;(1+each i._1+{.y),L:0 y }}
$(#~ 1 p: ])10#.&>([:[email protected];extend each)^:# >:i.9
100
10 10$(#~ 1 p: ])10#.&>([:[email protected];extend each)^:# >:i.9
2 3 13 23 5 7 17 37 47 67
127 137 347 157 257 457 167 367 467 1237
2347 2357 3457 1367 2467 3467 1567 4567 12347 12457
13457 13567 23567 123457 124567 19 29 59 79 89
139 239 149 349 359 269 569 179 379 479
389 1249 1259 1459 2459 3469 1279 1579 2579 4679
1289 2389 1489 2689 5689 1789 2789 4789 23459 13469
12569 12379 12479 13679 34679 15679 25679 12589 34589 12689
23689 13789 23789 123479 124679 235679 145679 345679 234589 345689
134789 125789 235789 245789 1245689 1234789 1235789 1456789 12356789 23456789
timex'(#~ 1 p: ])10#.&>([:[email protected];extend each)^:# >:i.9' NB. seconds (take with grain of salt)
0.003818
 

cpu here was a 1.2ghz i3-1005g1

jq[edit]

Works with: jq

Works with gojq, the Go implementation of jq

See Erdős-primes#jq for a suitable definition of `is_prime` as used here.

 
# Output: the stream of ascending primes, in order
def ascendingPrimes:
# Generate the stream of primes beginning with the digit .
# and with strictly ascending digits, without regard to order
def generate:
# strings
def g:
. as $first
| tonumber as $n
| select($n <= 9)
| $first,
((range($n + 1;10) | tostring | g) as $x
| $first + $x );
tostring | g | tonumber | select(is_prime);
 
[range(1;10) | generate] | sort[];
 
def task:
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
[ascendingPrimes]
| "There are \(length) ascending primes, namely:",
( _nwise(10) | map(lpad(10)) | join(" ") );
 
task
Output:
There are 100 ascending primes, namely:
         2          3          5          7         13         17         19         23         29         37
        47         59         67         79         89        127        137        139        149        157
       167        179        239        257        269        347        349        359        367        379
       389        457        467        479        569       1237       1249       1259       1279       1289
      1367       1459       1489       1567       1579       1789       2347       2357       2389       2459
      2467       2579       2689       2789       3457       3467       3469       4567       4679       4789
      5689      12347      12379      12457      12479      12569      12589      12689      13457      13469
     13567      13679      13789      15679      23459      23567      23689      23789      25679      34589
     34679     123457     123479     124567     124679     125789     134789     145679     234589     235679
    235789     245789     345679     345689    1234789    1235789    1245689    1456789   12356789   23456789


Julia[edit]

using Combinatorics
using Primes
 
function ascendingprimes()
return filter(isprime, [evalpoly(10, reverse(x))
for x in powerset([1, 2, 3, 4, 5, 6, 7, 8, 9]) if !isempty(x)])
end
 
foreach(p -> print(rpad(p[2], 10), p[1] % 10 == 0 ? "\n" : ""), enumerate(ascendingprimes()))
 
@time ascendingprimes()
 
 
Output:
2         3         5         7         13        17        19        23        29        37        
47        59        67        79        89        127       137       139       149       157       
167       179       239       257       269       347       349       359       367       379       
389       457       467       479       569       1237      1249      1259      1279      1289      
1367      1459      1489      1567      1579      1789      2347      2357      2389      2459      
2467      2579      2689      2789      3457      3467      3469      4567      4679      4789      
5689      12347     12379     12457     12479     12569     12589     12689     13457     13469     
13567     13679     13789     15679     23459     23567     23689     23789     25679     34589
34679     123457    123479    124567    124679    125789    134789    145679    234589    235679
235789    245789    345679    345689    1234789   1235789   1245689   1456789   12356789  23456789

0.000150 seconds (2.19 k allocations: 159.078 KiB

Lua[edit]

Exactly 511 calls to is_prime required.

local function is_prime(n)
if n < 2 then return false end
if n % 2 == 0 then return n==2 end
if n % 3 == 0 then return n==3 end
for f = 5, n^0.5, 6 do
if n%f==0 or n%(f+2)==0 then return false end
end
return true
end
 
local function ascending_primes()
local digits, candidates, primes = {1,2,3,4,5,6,7,8,9}, {0}, {}
for i = 1, #digits do
for j = 1, #candidates do
local value = candidates[j] * 10 + digits[i]
if is_prime(value) then primes[#primes+1] = value end
candidates[#candidates+1] = value
end
end
table.sort(primes)
return primes
end
 
print(table.concat(ascending_primes(), ", "))
Output:
2, 3, 5, 7, 13, 17, 19, 23, 29, 37, 47, 59, 67, 79, 89, 127, 137, 139, 149, 157, 167, 179, 239, 257, 269, 347, 349, 359, 367, 379, 389, 457, 467, 479, 569, 1237, 1249, 1259, 1279, 1289, 1367, 1459, 1489, 1567, 1579, 1789, 2347, 2357, 2389, 2459, 2467, 2579, 2689, 2789, 3457, 3467, 3469, 4567, 4679, 4789, 5689, 12347, 12379, 12457, 12479, 12569, 12589, 12689, 13457, 13469, 13567, 13679, 13789, 15679, 23459, 23567, 23689, 23789, 25679, 34589, 34679, 123457, 123479, 124567, 124679, 125789, 134789, 145679, 234589, 235679, 235789, 245789, 345679, 345689, 1234789, 1235789, 1245689, 1456789, 12356789, 23456789

Mathematica/Wolfram Language[edit]

[email protected][FromDigits /@ Subsets[[email protected], {1, \[Infinity]}], PrimeQ];
Multicolumn[ps, {Automatic, 6}, Appearance -> "Horizontal"]
Output:
2	3	5	7	13	17	19	23
29	37	47	59	67	79	89	127
137	139	149	157	167	179	239	257
269	347	349	359	367	379	389	457
467	479	569	1237	1249	1259	1279	1289
1367	1459	1489	1567	1579	1789	2347	2357
2389	2459	2467	2579	2689	2789	3457	3467
3469	4567	4679	4789	5689	12347	12379	12457
12479	12569	12589	12689	13457	13469	13567	13679
13789	15679	23459	23567	23689	23789	25679	34589
34679	123457	123479	124567	124679	125789	134789	145679
234589	235679	235789	245789	345679	345689	1234789	1235789
1245689	1456789	12356789	23456789

Perl[edit]

#!/usr/bin/perl
 
use strict; # https://rosettacode.org/wiki/Ascending_primes
use warnings;
use ntheory qw( is_prime );
 
print join('', map { sprintf "%10d", $_ } sort { $a <=> $b }
grep /./ && is_prime($_),
glob join '', map "{$_,}", 1 .. 9) =~ s/.{50}\K/\n/gr;
Output:
         2         3         5         7        13
        17        19        23        29        37
        47        59        67        79        89
       127       137       139       149       157
       167       179       239       257       269
       347       349       359       367       379
       389       457       467       479       569
      1237      1249      1259      1279      1289
      1367      1459      1489      1567      1579
      1789      2347      2357      2389      2459
      2467      2579      2689      2789      3457
      3467      3469      4567      4679      4789
      5689     12347     12379     12457     12479
     12569     12589     12689     13457     13469
     13567     13679     13789     15679     23459
     23567     23689     23789     25679     34589
     34679    123457    123479    124567    124679
    125789    134789    145679    234589    235679
    235789    245789    345679    345689   1234789
   1235789   1245689   1456789  12356789  23456789

Phix[edit]

with javascript_semantics
function ascending_primes(sequence res, atom p=0)
    for d=remainder(p,10)+1 to 9 do
        integer np = p*10+d
        if odd(d) and is_prime(np) then res &= np end if
        res = ascending_primes(res,np)
    end for
    return res
end function
 
sequence r = apply(true,sprintf,{{"%8d"},sort(ascending_primes({2}))})
printf(1,"There are %,d ascending primes:\n%s\n",{length(r),join_by(r,1,10," ")})
Output:
There are 100 ascending primes:
       2        3        5        7       13       17       19       23       29       37
      47       59       67       79       89      127      137      139      149      157
     167      179      239      257      269      347      349      359      367      379
     389      457      467      479      569     1237     1249     1259     1279     1289
    1367     1459     1489     1567     1579     1789     2347     2357     2389     2459
    2467     2579     2689     2789     3457     3467     3469     4567     4679     4789
    5689    12347    12379    12457    12479    12569    12589    12689    13457    13469
   13567    13679    13789    15679    23459    23567    23689    23789    25679    34589
   34679   123457   123479   124567   124679   125789   134789   145679   234589   235679
  235789   245789   345679   345689  1234789  1235789  1245689  1456789 12356789 23456789

powerset[edit]

Using a powerset, the basic idea of which was taken from the Factor entry above, here incrementally built, does not need either recursion or a sort, same output

with javascript_semantics
function ascending_primes()
    sequence res = {}, powerset = {0}
    while length(powerset) do
        sequence next = {}
        for i=1 to length(powerset) do
            for d=remainder(powerset[i],10)+1 to 9 do
                next &= powerset[i]*10+d
            end for
        end for
        powerset = next
        res &= filter(powerset,is_prime)
    end while
    return res
end function
 
sequence r = apply(true,sprintf,{{"%8d"},ascending_primes()})
printf(1,"There are %,d ascending primes:\n%s\n",{length(r),join_by(r,1,10," ")})

By way of explanation, specifically "no sort rqd", if you pp(shorten(powerset,"entries",3)) at the end of each iteration then you get:

{1,2,3, `...`, 7,8,9, ` (9 entries)`}
{12,13,14, `...`, 78,79,89, ` (36 entries)`}
{123,124,125, `...`, 679,689,789, ` (84 entries)`}
{1234,1235,1236, `...`, 5689,5789,6789, ` (126 entries)`}
{12345,12346,12347, `...`, 45789,46789,56789, ` (126 entries)`}
{123456,123457,123458, `...`, 346789,356789,456789, ` (84 entries)`}
{1234567,1234568,1234569, `...`, 2356789,2456789,3456789, ` (36 entries)`}
{12345678,12345679,12345689, `...`, 12456789,13456789,23456789, ` (9 entries)`}
{123456789}
{}

Picat[edit]

import util.
 
main =>
DP = [N : S in power_set("123456789"), S != [], N = S.to_int, prime(N)].sort,
foreach({P,I} in zip(DP,1..DP.len))
printf("%9d%s",P,cond(I mod 10 == 0,"\n",""))
end,
nl,
println(len=DP.len)
Output:
        2        3        5        7       13       17       19       23       29       37
       47       59       67       79       89      127      137      139      149      157
      167      179      239      257      269      347      349      359      367      379
      389      457      467      479      569     1237     1249     1259     1279     1289
     1367     1459     1489     1567     1579     1789     2347     2357     2389     2459
     2467     2579     2689     2789     3457     3467     3469     4567     4679     4789
     5689    12347    12379    12457    12479    12569    12589    12689    13457    13469
    13567    13679    13789    15679    23459    23567    23689    23789    25679    34589
    34679   123457   123479   124567   124679   125789   134789   145679   234589   235679
   235789   245789   345679   345689  1234789  1235789  1245689  1456789 12356789 23456789

len = 100


Quackery[edit]

powerset is defined at Power set#Quackery, and isprime is defined at Primality by trial division#Quackery.

  [ 0 swap witheach
[ swap 10 * + ] ] is digits->n ( [ --> n )
 
[]
' [ 1 2 3 4 5 6 7 8 9 ] powerset
witheach
[ digits->n dup isprime
iff join else drop ]
sort echo
Output:
[ 2 3 5 7 13 17 19 23 29 37 47 59 67 79 89 127 137 139 149 157 167 179 239 257 269 347 349 359 367 379 389 457 467 479 569 1237 1249 1259 1279 1289 1367 1459 1489 1567 1579 1789 2347 2357 2389 2459 2467 2579 2689 2789 3457 3467 3469 4567 4679 4789 5689 12347 12379 12457 12479 12569 12589 12689 13457 13469 13567 13679 13789 15679 23459 23567 23689 23789 25679 34589 34679 123457 123479 124567 124679 125789 134789 145679 234589 235679 235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789 ]

Raku[edit]

put (flat 2, 3, 5, 7, sort +*, gather (1..8).map: &recurse ).batch(10)».fmt("%8d").join: "\n";
 
sub recurse ($str) {
.take for ($str X~ (3, 7, 9)).grep: { .is-prime && [<] .comb };
recurse $str × 10 + $_ for $str % 10 ^.. 9;
}
 
printf "%.3f seconds", now - INIT now;
Output:
       2        3        5        7       13       17       19       23       29       37
      47       59       67       79       89      127      137      139      149      157
     167      179      239      257      269      347      349      359      367      379
     389      457      467      479      569     1237     1249     1259     1279     1289
    1367     1459     1489     1567     1579     1789     2347     2357     2389     2459
    2467     2579     2689     2789     3457     3467     3469     4567     4679     4789
    5689    12347    12379    12457    12479    12569    12589    12689    13457    13469
   13567    13679    13789    15679    23459    23567    23689    23789    25679    34589
   34679   123457   123479   124567   124679   125789   134789   145679   234589   235679
  235789   245789   345679   345689  1234789  1235789  1245689  1456789 12356789 23456789
0.075 seconds

Ring[edit]

This example is incorrect. Please fix the code and remove this message.
Details:
Many of the numbers shown do not have strictly ascending digits, e.g. all the ones starting with 9.
The single digit primes should also be included.
 
load "stdlibcore.ring"
 
limit = 1000
row = 0
 
for n = 1 to limit
flag = 0
strn = string(n)
if isprime(n) = 1
for m = 1 to len(strn)-1
if number(substr(strn,m)) > number(substr(strn,m+1))
flag = 1
ok
next
if flag = 1
row++
see "" + n + " "
ok
if row % 10 = 0
see nl
ok
ok
next
 

Output:

11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997

Sidef[edit]

func primes_with_ascending_digits(base = 10) {
 
var list = []
var digits = @(1..^base -> flip)
 
var end_digits = digits.grep { .is_coprime(base) }
list << digits.grep { .is_prime && !.is_coprime(base) }...
 
for k in (0 .. digits.end) {
digits.combinations(k, {|*a|
var v = a.digits2num(base)
end_digits.each {|d|
var n = (v*base + d)
next if ((n >= base) && (a[0] >= d))
list << n if (n.is_prime)
}
})
}
 
list.sort
}
 
var arr = primes_with_ascending_digits()
 
say "There are #{arr.len} ascending primes.\n"
 
arr.each_slice(10, {|*a|
say a.map { '%8s' % _ }.join(' ')
})
Output:
There are 100 ascending primes.

       2        3        5        7       13       17       19       23       29       37
      47       59       67       79       89      127      137      139      149      157
     167      179      239      257      269      347      349      359      367      379
     389      457      467      479      569     1237     1249     1259     1279     1289
    1367     1459     1489     1567     1579     1789     2347     2357     2389     2459
    2467     2579     2689     2789     3457     3467     3469     4567     4679     4789
    5689    12347    12379    12457    12479    12569    12589    12689    13457    13469
   13567    13679    13789    15679    23459    23567    23689    23789    25679    34589
   34679   123457   123479   124567   124679   125789   134789   145679   234589   235679
  235789   245789   345679   345689  1234789  1235789  1245689  1456789 12356789 23456789

Vlang[edit]

Translation of: Go
fn is_prime(n int) bool {
if n < 2 {
return false
} else if n%2 == 0 {
return n == 2
} else if n%3 == 0 {
return n == 3
} else {
mut d := 5
for d*d <= n {
if n%d == 0 {
return false
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
fn generate(first int, cand int, digits int, mut asc map[int]bool) {
if digits == 0 {
if is_prime(cand) {
asc[cand] = true
}
return
}
for i in first..10 {
next := cand*10 + i
generate(i+1, next, digits-1, mut asc)
}
}
 
fn main() {
mut asc_primes_set := map[int]bool{} // avoids duplicates
 
for digits in 1..10 {
generate(1, 0, digits, mut asc_primes_set)
}
le := asc_primes_set.keys().len
mut asc_primes := []int{len: le}
mut i := 0
for k,_ in asc_primes_set {
asc_primes[i] = k
i++
}
asc_primes.sort()
println("There are $le ascending primes, namely:")
for q in 0..le {
print("${asc_primes[q]:8} ")
if (q+1)%10 == 0 {
println('')
}
}
}
Output:
There are 100 ascending primes, namely:
       2        3        5        7       13       17       19       23       29       37 
      47       59       67       79       89      127      137      139      149      157 
     167      179      239      257      269      347      349      359      367      379 
     389      457      467      479      569     1237     1249     1259     1279     1289 
    1367     1459     1489     1567     1579     1789     2347     2357     2389     2459 
    2467     2579     2689     2789     3457     3467     3469     4567     4679     4789 
    5689    12347    12379    12457    12479    12569    12589    12689    13457    13469 
   13567    13679    13789    15679    23459    23567    23689    23789    25679    34589 
   34679   123457   123479   124567   124679   125789   134789   145679   234589   235679 
  235789   245789   345679   345689  1234789  1235789  1245689  1456789 12356789 23456789 

Wren[edit]

Library: Wren-math
Library: Wren-seq
Library: Wren-fmt

Version 1 (Sieve)[edit]

Although they use a lot of memory, sieves usually produce good results in Wren and here we only need to sieve for primes up to 3456789 as there are just 9 possible candidates with 8 digits and 1 possible candidate with 9 digits which we can test for primality individually. The following runs in around 0.43 seconds.

import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
 
var isAscending = Fn.new { |n|
if (n < 10) return true
var digits = Int.digits(n)
for (i in 1...digits.count) {
if (digits[i] <= digits[i-1]) return false
}
return true
}
 
var higherPrimes = []
var candidates = [
12345678, 12345679, 12345689, 12345789, 12346789,
12356789, 12456789, 13456789, 23456789, 123456789
]
for (cand in candidates) if (Int.isPrime(cand)) higherPrimes.add(cand)
 
var primes = Int.primeSieve(3456789)
var ascPrimes = []
for (p in primes) if (isAscending.call(p)) ascPrimes.add(p)
ascPrimes.addAll(higherPrimes)
System.print("There are %(ascPrimes.count) ascending primes, namely:")
for (chunk in Lst.chunks(ascPrimes, 10)) Fmt.print("$8d", chunk)
Output:
There are 100 ascending primes, namely:
       2        3        5        7       13       17       19       23       29       37
      47       59       67       79       89      127      137      139      149      157
     167      179      239      257      269      347      349      359      367      379
     389      457      467      479      569     1237     1249     1259     1279     1289
    1367     1459     1489     1567     1579     1789     2347     2357     2389     2459
    2467     2579     2689     2789     3457     3467     3469     4567     4679     4789
    5689    12347    12379    12457    12479    12569    12589    12689    13457    13469
   13567    13679    13789    15679    23459    23567    23689    23789    25679    34589
   34679   123457   123479   124567   124679   125789   134789   145679   234589   235679
  235789   245789   345679   345689  1234789  1235789  1245689  1456789 12356789 23456789

Version 2 (Generator)[edit]

Library: Wren-set

Here we generate all possible positive integers with ascending non-zero digits and filter out those that are prime.

Much quicker than the 'sieve' approach at 0.013 seconds. I also tried using a powerset but that was slightly slower at 0.015 seconds.

import "./set" for Set
import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
 
var ascPrimes = Set.new() // avoids duplicates
 
var generate // recursive function
generate = Fn.new { |first, cand, digits|
if (digits == 0) {
if (Int.isPrime(cand)) ascPrimes.add(cand)
return
}
var i = first
while (i <= 9) {
var next = cand * 10 + i
generate.call(i + 1, next, digits - 1)
i = i + 1
}
}
 
for (digits in 1..9) generate.call(1, 0, digits)
ascPrimes = ascPrimes.toList
ascPrimes.sort()
System.print("There are %(ascPrimes.count) ascending primes, namely:")
for (chunk in Lst.chunks(ascPrimes, 10)) Fmt.print("$8s", chunk)
Output:
Same as before.

XPL0[edit]

Brute force solution: 4.3 seconds on Pi4.

func IsPrime(N);        \Return 'true' if N is prime
int N, I;
[if N <= 2 then return N = 2;
if (N&1) = 0 then \even >2\ return false;
for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1;
];
return true;
];
 
func Ascending(N); \Return 'true' if digits are ascending
int N, D;
[N:= N/10;
D:= rem(0);
while N do
[N:= N/10;
if rem(0) >= D then return false;
D:= rem(0);
];
return true;
];
 
int Cnt, N;
[Cnt:= 0;
Format(9, 0);
for N:= 2 to 123_456_789 do
if Ascending(N) then
if IsPrime(N) then
[RlOut(0, float(N));
Cnt:= Cnt+1;
if rem(Cnt/10) = 0 then CrLf(0);
];
]
Output:
        2        3        5        7       13       17       19       23       29       37
       47       59       67       79       89      127      137      139      149      157
      167      179      239      257      269      347      349      359      367      379
      389      457      467      479      569     1237     1249     1259     1279     1289
     1367     1459     1489     1567     1579     1789     2347     2357     2389     2459
     2467     2579     2689     2789     3457     3467     3469     4567     4679     4789
     5689    12347    12379    12457    12479    12569    12589    12689    13457    13469
    13567    13679    13789    15679    23459    23567    23689    23789    25679    34589
    34679   123457   123479   124567   124679   125789   134789   145679   234589   235679
   235789   245789   345679   345689  1234789  1235789  1245689  1456789 12356789 23456789

powerset[edit]

Aaah! Power set, from Factor. Runs in less than 1 millisecond. A better way of measuring duration than using Linux's time utility gave a more credible 35 milliseconds.

include xpllib;         \provides IsPrime and Sort
 
int I, N, Mask, Digit, A(512), Cnt;
[for I:= 0 to 511 do
[N:= 0; Mask:= I; Digit:= 1;
while Mask do
[if Mask&1 then
N:= N*10 + Digit;
Mask:= Mask>>1;
Digit:= Digit+1;
];
A(I):= N;
];
Sort(A, 512);
Cnt:= 0;
Format(9, 0);
for I:= 1 to 511 do \skip empty set
[N:= A(I);
if IsPrime(N) then
[RlOut(0, float(N));
Cnt:= Cnt+1;
if rem(Cnt/10) = 0 then CrLf(0);
];
];
]
Output:
Same as before.