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
- Primes with digits in nondecreasing order (infinite series allowing duplicate digits, whereas this isn't and doesn't)
- Pandigital prime (whereas this is the smallest, with gaps in the used digits being permitted)
ALGOL 68
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...).
<lang algol68>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</lang>
- 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
<lang rebol>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
]</lang>
- 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
<lang AWK>
- 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)
} </lang>
- 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
C
<lang C>/*
* Ascending primes * * Generate and show all primes with strictly ascending decimal digits. * * * Solution * * We only consider positive numbers in the range 1 to 123456789. We would * get 7027260 primes, because there are so many primes smaller than 123456789 * (see also Wolfram Alpha).On the other hand, there are only 511 distinct * positive integers having their digits arranged in ascending order. * Therefore, it is better to start with numbers that have properly arranged * digitsand then check if they are prime numbers.The method of generating * a sequence of such numbers is not indifferent.We want this sequence to be * monotonically increasing, because then additional sorting of results will * be unnecessary. It turns out that by using a queue we can easily get the * desired effect. Additionally, the algorithm then does not use recursion * (although the program probably does not have to comply with the MISRA * standard). The problem to be solved is the queue size, the a priori * assumption that 1000 is good enough, but a bit magical. */
- include <stdio.h>
- include <stdlib.h>
- include <stdbool.h>
- include <math.h>
- if UINT_MAX < 123456789
- error "we need at least 9 decimal digits (32-bit integers)"
- endif
- define MAXSIZE 1000
unsigned queue[MAXSIZE]; unsigned primes[MAXSIZE];
unsigned begin = 0; unsigned end = 0; unsigned n = 0;
bool isPrime(unsigned n)
{
if (n == 0 || n == 1) { return false; } else if (n != 2) { if (n % 2 == 0) { return false; } unsigned root = sqrt(n); for (unsigned k = 3; k <= root; k += 2) { if (n % k == 0) { return false; } } } return true;
}
int main(int argc, char argv[])
{
for (int k = 1; k <= 9; k++) { queue[end++] = k; }
while (begin < end) { int value = queue[begin++]; if (isPrime(value)) { primes[n++] = value; } for (int k = value % 10 + 1; k <= 9; k++) { queue[end++] = value * 10 + k; } }
for (int k = 0; k < n; k++) { printf("%u ", primes[k]); } return EXIT_SUCCESS;
}</lang>
- 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
C++
<lang Cpp>/*
* Ascending primes * * Generate and show all primes with strictly ascending decimal digits. * * * Solution * * We only consider positive numbers in the range 1 to 123456789. We would * get 7027260 primes, because there are so many primes smaller than 123456789 * (see also Wolfram Alpha).On the other hand, there are only 511 distinct * positive integers having their digits arranged in ascending order. * Therefore, it is better to start with numbers that have properly arranged * digitsand then check if they are prime numbers.The method of generating * a sequence of such numbers is not indifferent.We want this sequence to be * monotonically increasing, because then additional sorting of results will * be unnecessary. It turns out that by using a queue we can easily get the * desired effect. Additionally, the algorithm then does not use recursion * (although the program probably does not have to comply with the MISRA * standard). The problem to be solved is the queue size, the a priori * assumption that 1000 is good enough, but a bit magical. */
- include <cmath>
- include <iostream>
- include <queue>
- include <vector>
using namespace std;
queue<unsigned> suspected;
vector<unsigned> primes;
bool isPrime(unsigned n)
{
if (n == 0 || n == 1) { return false; } else if (n != 2) { if (n % 2 == 0) { return false; } else { unsigned root = sqrt(n); for (unsigned k = 3; k <= root; k += 2) { if (n % k == 0) { return false; } } } } return true;
}
int main(int argc, char argv[])
{
for (unsigned k = 1; k <= 9; k++) { suspected.push(k); }
while (!suspected.empty()) { int n = suspected.front(); suspected.pop();
if (isPrime(n)) { primes.push_back(n); }
// The value of n % 10 gives the least significient digit of n // for (unsigned k = n % 10 + 1; k <= 9; k++) { suspected.push(n * 10 + k); } }
copy(primes.begin(), primes.end(), ostream_iterator<unsigned>(cout, " "));
return EXIT_SUCCESS;
}</lang>
- 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
C#
<lang Csharp> </lang>
- Output:
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // 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 ""
</lang>
- 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
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.
<lang factor>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.</lang>
- 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
Fortran
<lang Fortran>! Ascending primes ! ! Generate and show all primes with strictly ascending decimal digits. ! ! ! Solution ! ! We only consider positive numbers in the range 1 to 123456789. We would get ! 7027260 primes, because there are so many primes smaller than 123456789 (see ! also Wolfram Alpha). On the other hand, there are only 511 distinct positive ! integers having their digits arranged in ascending order. Therefore, it is ! better to start with numbers that have properly arranged digits and then check ! if they are prime numbers. The method of generating a sequence of such numbers ! is not indifferent. We want this sequence to be monotonically increasing, ! because then additional sorting of results will be unnecessary. It turns out ! that by using a queue we can easily get the desired effect. Additionally, the ! algorithm then does not use recursion (although the program probably does not ! have to comply with the MISRA standard). The problem to be solved is the queue ! size, the a priori assumption that 1000 is good enough, but a bit magical.
program prog
parameter (MAXSIZE = 1000) logical isprime dimension iqueue(MAXSIZE) dimension iprimes(MAXSIZE) ibegin = 1 iend = 1 n = 0
do k = 1, 9 iqueue(iend) = k iend = iend + 1 end do do while (ibegin .lt. iend) iv = iqueue(ibegin) ibegin = ibegin + 1 if (isprime(iv)) then n = n + 1 iprimes(n) = iv end if lsd1 = mod(iv, 10) + 1 if (lsd1 .le. 9) then do k = lsd1, 9 iqueue(iend) = iv * 10 + k iend = iend + 1 end do end if end do
print *, (iprimes(i), i = 1, n)
end program
logical function isprime(n)
! Slightly improved algorithm for checking if a number is prime. ! First, we check the special cases: 0, 1, 2. Then we check whether ! the number is divisible by 2. If it is not divisible by two, ! we check whether it is divisible by odd numbers not greater than ! the square root of that number. ! ! Positive numbers only. BTW, negative numbers are prime numbers ! if their absolute values are prime numbers.
isprime = .FALSE. if (n .eq. 0 .or. n .eq. 1) then return end if if (n .ne. 2) then if (mod(n, 2) .eq. 0) then return end if m = n**0.5 do k = 3, m, 2 if (mod(n, k) .eq. 0) then return end if end do end if isprime = .TRUE.
end function</lang>
- Output:
The estimated execution time is 1.5 milliseconds on the same hardware on which the Java program was run. It should be remembered that modern CPUs do not have a constant clock speed and additionally the measured times depend on the system load with other tasks. Nevertheless, the Fortran program seems to be 4 times faster than the Java program.
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
Using a generator. <lang go>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() } }
}</lang>
- 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
Compare with Descending primes.
<lang J> extend=: {{ y;(1+each i._1+{.y),L:0 y }}
$(#~ 1 p: ])10#.&>([:~.@;extend each)^:# >:i.9
100
10 10$(#~ 1 p: ])10#.&>([:~.@;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#.&>([:~.@;extend each)^:# >:i.9' NB. seconds (take with grain of salt)
0.003818 </lang>
cpu here was a 1.2ghz i3-1005g1
Java
<lang Java>/*
* Ascending primes * * Generate and show all primes with strictly ascending decimal digits. * * * Solution * * We only consider positive numbers in the range 1 to 123456789. We would * get 7027260 primes, because there are so many primes smaller than 123456789 * (see also Wolfram Alpha).On the other hand, there are only 511 distinct * positive integers having their digits arranged in ascending order. * Therefore, it is better to start with numbers that have properly arranged * digits and then check if they are prime numbers.The method of generating * a sequence of such numbers is not indifferent.We want this sequence to be * monotonically increasing, because then additional sorting of results will * be unnecessary. It turns out that by using a queue we can easily get the * desired effect. Additionally, the algorithm then does not use recursion * (although the program probably does not have to comply with the MISRA * standard). The problem to be solved is the queue size, the a priori * assumption that 1000 is good enough, but a bit magical. */
package example.rossetacode.ascendingprimes;
import java.util.Arrays;
public class Program implements Runnable {
public static void main(String[] args) { long t1 = System.nanoTime(); new Program().run(); long t2 = System.nanoTime(); System.out.println( "total time consumed = " + (t2 - t1) * 1E-6 + " milliseconds"); }
public void run() {
final int MAX_SIZE = 1000; final int[] queue = new int[MAX_SIZE]; int begin = 0; int end = 0;
for (int k = 1; k <= 9; k++) { queue[end++] = k; }
while (begin < end) { int n = queue[begin++]; for (int k = n % 10 + 1; k <= 9; k++) { queue[end++] = n * 10 + k; } }
// We can use parallel stream (and sort results) to use multiple cores. // System.out.println(Arrays.stream(queue).filter(this::isPrime).boxed().toList()); }
private boolean isPrime(int value) { if (value == 0 || value == 1) return false; if (value != 2) { if (value % 2 == 0) { return false; } int root = (int) Math.sqrt(value); for (int k = 3; k <= root; k += 2) if (value % k == 0) { return false; } } return true; }
}</lang>
- 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] total time consumed = 4.964799999999999 milliseconds
JavaScript
<lang javascript><!DOCTYPE html> <html> <body>
<noscript> No script, no fun. Turn on Javascript on. </noscript>
<script> (()=>{
function isPrime(n) { if (n == 0 || n == 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; root = Math.sqrt(n) for (let k = 3; k <= root; k += 2) if (n % k == 0) return false; return true; }
let queue = []; let primes = [];
for (let k = 1; k <= 9; k++) queue.push(k);
while (queue.length != 0) { let n = queue.shift(); if (isPrime(n)) primes.push(n); for (let k = n % 10 + 1; k <= 9; k++) queue.push(n * 10 + k); }
document.writeln(primes);
})(); </script>
</body> </html></lang>
- 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
jq
Works with gojq, the Go implementation of jq
See Erdős-primes#jq for a suitable definition of `is_prime` as used here.
<lang jq>
- 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</lang>
- 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
<lang julia>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()
</lang>
- 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
Exactly 511 calls to is_prime
required.
<lang Lua>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(), ", "))</lang>
- 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
<lang Mathematica>ps=Sort@Select[FromDigits /@ Subsets[Range@9, {1, \[Infinity]}], PrimeQ]; Multicolumn[ps, {Automatic, 6}, Appearance -> "Horizontal"]</lang>
- 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
<lang perl>#!/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;</lang>
- 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
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
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} {}
PHP
<lang php><?php
function isPrime($n) {
if ($n == 0 || $n == 1) return false; if ($n == 2) return true; $root = intval(sqrt($n)); for ($k = 2; $k <= $root; $k += 2) if ($n % $k == 0) return false; return true;
}
$queue = []; $primes = [];
$begin = 0; $end = 0;
for ($k = 1; $k <= 9; $k++)
$queue[$end++] = $k;
while ($begin < $end) {
$n = $queue[$begin++]; if (isPrime($n)) $primes[] = $n; for ($k = $n % 10 + 1; $k <= 9; $k++) $queue[$end++] = $n * 10 + $k;
}
foreach($primes as $p)
echo "$p ";</lang>
- Output:
2 3 5 7 9 13 15 17 19 23 25 27 29 35 37 39 45 47 49 57 59 67 69 79 89 123 125 127 129 135 137 139 145 147 149 157 159 167 169 179 189 235 237 239 245 247 249 257 259 267 269 279 289 345 347 349 357 359 367 369 379 389 457 459 467 469 479 489 567 569 579 589 679 689 789 1235 1237 1239 1245 1247 1249 1257 1259 1267 1269 1279 1289 1345 1347 1349 1357 1359 1367 1369 1379 1389 1457 1459 1467 1469 1479 1489 1567 1569 1579 1589 1679 1689 1789 2345 2347 2349 2357 2359 2367 2369 2379 2389 2457 2459 2467 2469 2479 2489 2567 2569 2579 2589 2679 2689 2789 3457 3459 3467 3469 3479 3489 3567 3569 3579 3589 3679 3689 3789 4567 4569 4579 4589 4679 4689 4789 5679 5689 5789 6789 12345 12347 12349 12357 12359 12367 12369 12379 12389 12457 12459 12467 12469 12479 12489 12567 12569 12579 12589 12679 12689 12789 13457 13459 13467 13469 13479 13489 13567 13569 13579 13589 13679 13689 13789 14567 14569 14579 14589 14679 14689 14789 15679 15689 15789 16789 23457 23459 23467 23469 23479 23489 23567 23569 23579 23589 23679 23689 23789 24567 24569 24579 24589 24679 24689 24789 25679 25689 25789 26789 34567 34569 34579 34589 34679 34689 34789 35679 35689 35789 36789 45679 45689 45789 46789 56789 123457 123459 123467 123469 123479 123489 123567 123569 123579 123589 123679 123689 123789 124567 124569 124579 124589 124679 124689 124789 125679 125689 125789 126789 134567 134569 134579 134589 134679 134689 134789 135679 135689 135789 136789 145679 145689 145789 146789 156789 234567 234569 234579 234589 234679 234689 234789 235679 235689 235789 236789 245679 245689 245789 246789 256789 345679 345689 345789 346789 356789 456789 1234567 1234569 1234579 1234589 1234679 1234689 1234789 1235679 1235689 1235789 1236789 1245679 1245689 1245789 1246789 1256789 1345679 1345689 1345789 1346789 1356789 1456789 2345679 2345689 2345789 2346789 2356789 2456789 3456789 12345679 12345689 12345789 12346789 12356789 12456789 13456789 23456789 123456789
Picat
<lang Picat>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)</lang>
- 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
PicoLisp
<lang PicoLisp>(de prime? (N)
(or (= N 2) (and (> N 1) (bit? 1 N) (for (D 3 T (+ D 2)) (T (> D (sqrt N)) T) (T (=0 (% N D)) NIL) ) ) ) )
(let
(D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) Lst (make (while (>= 23456789 D) (and (prime? D) (apply < (chop D)) (link D) ) (inc 'D (++ L)) ) ) ) (let Fmt (need 10 10) (while (cut 10 'Lst) (apply tab @ Fmt) ) ) )</lang>
- 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
Python
[The isprime
here is taken from sympy module, but any of the functions of the same name from other tasks on this site would work.] -- this is a false assumption, e.g. def isprime(n): return "Fat boy" has `the same name` but can not be used here!
<lang Python>from sympy import isprime
def ascending(x=0):
for y in range(x*10 + (x%10) + 1, x*10 + 10): yield from ascending(y) yield(y)
print(sorted(x for x in ascending() if isprime(x)))</lang>
- 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]
Quackery
powerset
is defined at Power set#Quackery, and isprime
is defined at Primality by trial division#Quackery.
<lang 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</lang>
- 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
<lang perl6>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;</lang>
- 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
<lang ring> 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 </lang> 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
Ruby
<lang ruby>require 'prime'
digits = [9,8,7,6,5,4,3,2,1] res = 1.upto(digits.size).flat_map do |n|
digits.combination(n).filter_map do |set| candidate = set.join.to_i candidate if candidate.prime? end.reverse end
puts res.join(",")</lang>
- 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
Sidef
<lang ruby>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(' ')
})</lang>
- 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
Visual Basic .NET
One method is to use recursion. Another method (see example in Fortran) is to use a queue to obtain sorted results and avoid recursion. Below is a third way: simply "every problem can be solved with just the right number of for loops". Have fun. <lang vbnet>Module Module1
Function isprime(n As Integer) If n = 0 Then Return False End If If n = 1 Then Return False End If If n = 2 Then Return True End If If n = 3 Then Return True End If If n = 4 Then Return False End If If n = 5 Then Return True End If For k = 2 To n - 1 If n Mod k = 0 Then Return False End If Next Return True End Function
Sub Main() Dim x As Integer Dim y As ArrayList = New ArrayList(1000)
For d8 = 1 To 9 x = d8 If isprime(x) Then y.Add(x) End If For d7 = d8 + 1 To 9 x = (d8 * 10) + d7 If isprime(x) Then y.Add(x) End If For d6 = d7 + 1 To 9 x = ((d8 * 10) + d7) * 10 + d6 If isprime(x) Then y.Add(x) End If For d5 = d6 + 1 To 9 x = (((d8 * 10) + d7) * 10 + d6) * 10 + d5 If isprime(x) Then y.Add(x) End If For d4 = d5 + 1 To 9 x = ((((d8 * 10) + d7) * 10 + d6) * 10 + d5) * 10 + d4 If isprime(x) Then y.Add(x) End If For d3 = d4 + 1 To 9 x = (((((d8 * 10) + d7) * 10 + d6) * 10 + d5) * 10 + d4) * 10 + d3 If isprime(x) Then y.Add(x) End If For d2 = d3 + 1 To 9 x = ((((((d8 * 10) + d7) * 10 + d6) * 10 + d5) * 10 + d4) * 10 + d3) * 10 + d2 If isprime(x) Then y.Add(x) End If For d1 = d2 + 1 To 9 x = (((((((d8 * 10) + d7) * 10 + d6) * 10 + d5) * 10 + d4) * 10 + d3) * 10 + d2) * 10 + d1 If isprime(x) Then y.Add(x) End If For d0 = d1 + 1 To 9 x = ((((((((d8 * 10) + d7) * 10 + d6) * 10 + d5) * 10 + d4) * 10 + d3) * 10 + d2) * 10 + d1) * 10 + d0 If isprime(x) Then y.Add(x) End If Next Next Next Next Next Next Next Next Next
y.Sort() For Each z As Integer In y Console.Write(z) Console.Write(" ") Next Console.WriteLine()
End Sub
End Module </lang>
- 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
Vlang
<lang vlang>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() } }
}</lang>
- 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
Version 1 (Sieve)
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. <lang ecmascript>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)</lang>
- 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)
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. <lang ecmascript>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)</lang>
- Output:
Same as before.
XPL0
Brute force solution: 4.3 seconds on Pi4. <lang XPL0>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); ];
]</lang>
- 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
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. <lang XPL0>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); ]; ];
]</lang>
- Output:
Same as before.
- Programming Tasks
- Solutions by Programming Task
- ALGOL 68
- ALGOL 68-primes
- ALGOL 68-rows
- Arturo
- AWK
- C
- C++
- C sharp
- F Sharp
- Factor
- Fortran
- Go
- Go-rcu
- J
- Java
- JavaScript
- Jq
- Julia
- Lua
- Mathematica
- Wolfram Language
- Perl
- Phix
- PHP
- Picat
- PicoLisp
- Python
- Quackery
- Raku
- Ring
- Ring examples needing attention
- Examples needing attention
- Ruby
- Sidef
- Visual Basic .NET
- Vlang
- Wren
- Wren-math
- Wren-seq
- Wren-fmt
- Wren-set
- XPL0