Rosetta Code

Ascending primes: Difference between revisions

Page Discussion

Ascending primes (view source)

Revision as of 09:01, 23 December 2023

12,197 bytes added ,  5 months ago
m
no edit summary
mNo edit summary
 
(15 intermediate revisions by 9 users not shown)
Line 16:
*[[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)
*[[Descending primes]]
 
 
Line 111 ⟶ 112:
34679 123457 123479 124567 124679 125789 134789 145679 234589 235679
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789
</pre>
 
=={{header|ALGOL W}}==
{{Trans|Lua}}
...and only a few characters different from the Algol W [[Descending primes]] sample.
<syntaxhighlight lang="algolw">
begin % find all primes with strictly ascending digits - translation of Lua %
 
% quicksorts v, the bounds of v must be specified in lb and ub %
procedure quicksort ( integer array v( * )
; integer value lb, ub
) ;
if ub > lb then begin
% more than one element, so must sort %
integer left, right, pivot;
left := lb;
right := ub;
% choosing the middle element of the array as the pivot %
pivot := v( left + ( ( right + 1 ) - left ) div 2 );
while begin
while left <= ub and v( left ) < pivot do left := left + 1;
while right >= lb and v( right ) > pivot do right := right - 1;
left <= right
end do begin
integer swap;
swap := v( left );
v( left ) := v( right );
v( right ) := swap;
left := left + 1;
right := right - 1
end while_left_le_right ;
quicksort( v, lb, right );
quicksort( v, left, ub )
end quicksort ;
 
% returns true if n is prime, false otherwise %
logical procedure is_prime( integer value n ) ;
if n < 2 then false
else if n rem 2 = 0 then n = 2
else if n rem 3 = 0 then n = 3
else begin
logical prime; prime := true;
for f := 5 step 6 until entier( sqrt( n ) ) do begin
if n rem f = 0 or n rem ( f + 2 ) = 0 then begin
prime := false;
goto done
end if_n_rem_f_eq_0_or_n_rem_f_plus_2_eq_0
end for_f;
done: prime
end is_prime ;
 
% increments n and also returns its new value %
integer procedure inc ( integer value result n ) ; begin n := n + 1; n end;
 
% sets primes to the list of ascending primes and lenPrimes to the %
% number of ascending primes - primes must be big enough, e.g. have 511 %
% elements %
procedure ascending_primes ( integer array primes ( * )
; integer result lenPrimes
) ;
begin
integer array digits ( 1 :: 9 );
integer array candidates ( 1 :: 6000 );
integer lenCandidates;
candidates( 1 ) := 0;
lenCandidates := 1;
lenPrimes := 0;
for i := 1 until 9 do digits( i ) := i;
for i := 1 until 9 do begin
for j := 1 until lenCandidates do begin
integer cValue; cValue := candidates( j ) * 10 + digits( i );
if is_prime( cValue ) then primes( inc( lenPrimes ) ) := cValue;
candidates( inc( lenCandidates ) ) := cValue
end for_j
end for_i ;
quickSort( primes, 1, lenPrimes );
end ascending_primes ;
 
begin % find the ascending primes and print them %
integer array primes ( 1 :: 512 );
integer lenPrimes;
ascending_primes( primes, lenPrimes );
for i := 1 until lenPrimes do begin
writeon( i_w := 8, s_w := 0, " ", primes( i ) );
if i rem 10 = 0 then write()
end for_i
end
end.
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
Line 575 ⟶ 677:
{{out}}
<pre>{stretchy vector 2, 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}</pre>
 
=={{header|EasyLang}}==
 
This outputs all 100 ascending primes. They are not sorted - that was not demanded anyway.
 
<syntaxhighlight lang=easylang>
func isprim num .
if num < 2
return 0
.
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
proc nextasc n . .
if isprim n = 1
write n & " "
.
if n > 123456789
return
.
for d = n mod 10 + 1 to 9
nextasc n * 10 + d
.
.
nextasc 0
</syntaxhighlight>
 
 
=={{header|F_Sharp|F#}}==
Line 587 ⟶ 722:
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
</pre>
 
=={{header|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.
Line 773 ⟶ 909:
235789 245789 345679 345689 1234789 1235789
1245689 1456789 12356789 23456789
</pre>
 
=={{header|FreeBASIC}}==
===Power Set===
{{trans|XPL0}}
<syntaxhighlight lang="vb">#include "isprime.bas"
#include "sort.bas"
 
Dim As Integer i, n, tmp, num, cant = 0
Dim Shared As Integer matriz(512)
For i = 0 To Ubound(matriz)-1
n = 0
tmp = i
num = 1
While tmp
If tmp And 1 Then n = n * 10 + num
tmp Shr= 1
num += 1
Wend
matriz(i)= n
Next i
 
Sort(matriz())
 
For i = 1 To Ubound(matriz)-1 'skip empty set
n = matriz(i)
If isPrime(n) Then
Print Using "#########"; n;
cant += 1
If cant Mod 10 = 0 Then Print
End If
Next i
Print Using !"\nThere are & ascending primes."; cant
 
Sleep</syntaxhighlight>
 
 
{{out}}
<pre> 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
 
There are 100 ascending primes.</pre>
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
local fn IsPrime( n as NSUInteger ) as BOOL
BOOL isPrime = YES
NSUInteger i
if n < 2 then exit fn = NO
if n = 2 then exit fn = YES
if n mod 2 == 0 then exit fn = NO
for i = 3 to int(n^.5) step 2
if n mod i == 0 then exit fn = NO
next
end fn = isPrime
 
void local fn AscendingPrimes( limit as long )
long i, n, mask, num, count = 0
for i = 0 to limit -1
n = 0 : mask = i : num = 1
while ( mask )
if mask & 1 then n = n * 10 + num
mask = mask >> 1
num++
wend
mda(i) = n
next
mda_sort @"compare:"
for i = 1 to mda_count (0) - 1
n = mda_integer(i)
if ( fn IsPrime( n ) )
printf @"%10ld\b", n
count++
if count mod 10 == 0 then print
end if
next
printf @"\n\tThere are %ld ascending primes.", count
end fn
 
window 1, @"Ascending Primes", ( 0, 0, 780, 230 )
print
 
CFTimeInterval t
t = fn CACurrentMediaTime
fn AscendingPrimes( 512 )
printf @"\n\tCompute time: %.3f ms\n",(fn CACurrentMediaTime-t)*1000
 
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
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
 
There are 100 ascending primes.
 
Compute time: 9.008 ms
</pre>
 
Line 839 ⟶ 1,092:
 
=={{header|J}}==
Compare with [[Descending_primes#J|Descending primes]].
 
[https://jsoftware.github.io/j-playground/bin/html/#code=_10%20%5D%5C%20%2F%3A~%20(%23~%201%26p%3A)%2010%26%23.%40I.%20%23%3A%20i.%20513 Live link].
Compare with [[Descending primes#J|Descending primes]].
<syntaxhighlight lang="j">_10 ]\ /:~ (#~ 1&p:) 10&#.@I. #: i. 513</syntaxhighlight>
 
{{out}}
[https://jsoftware.github.io/j-playground/bin/html/emj.html#code=%20%20%20extend%3D%3A%20%7B%7B%20y%3B(1%2Beach%20i._1%2B%7B.y)%2CL%3A0%20y%20%7D%7D%0D%0A%20%20%2010%2010%24(%23~%201%20p%3A%20%5D)10%23.%26%3E(%5B%3A~.%40%3Bextend%20each)%5E%3A%23%20%3E%3Ai.9 Live link].
<pre>
 
2 3 5 7 13 17 19 23 29 37
<syntaxhighlight lang="j"> extend=: {{ y;(1+each i._1+{.y),L:0 y }}
47 59 67 79 89 127 137 139 149 157
$(#~ 1 p: ])10#.&>([:~.@;extend each)^:# >:i.9
167 179 239 257 269 347 349 359 367 379
100
389 457 467 479 569 1237 1249 1259 1279 1289
10 10$(#~ 1 p: ])10#.&>([:~.@;extend each)^:# >:i.9
1367 21459 1489 31567 1579 13 1789 23 2347 2357 5 2389 7 17 37 47 672459
2467 127 2579 137 2689 3472789 1573457 3467 257 3469 457 4567 167 4679 367 467 12374789
23475689 12347 2357 12379 345712457 136712479 12569 2467 12589 3467 12689 1567 13457 4567 12347 1245713469
13457 13567 2356713679 123457 13789 124567 15679 23459 19 23567 29 59 23689 23789 79 25679 8934589
34679 123457 123479 124567 124679 125789 134789 145679 234589 235679
139 239 149 349 359 269 569 179 379 479
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789
389 1249 1259 1459 2459 3469 1279 1579 2579 4679
</pre>
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'
0.003818
</syntaxhighlight>
 
cpu here was a 1.2ghz i3-1005g1 and <code>timex</code> here reported the time (in seconds) to execute the quoted sentence once.
 
=={{header|Java}}==
Line 1,190 ⟶ 1,436:
234589 235679 235789 245789 345679 345689 1234789 1235789
1245689 1456789 12356789 23456789</pre>
 
=={{header|Nim}}==
We build the candidates using a loop by increasing length. Our solution needs only 502 primality tests.
<syntaxhighlight lang="Nim">import std/[strutils, sugar]
 
proc isPrime(n: int): bool =
assert n > 7
if n mod 2 == 0 or n mod 3 == 0: return false
var d = 5
var step = 2
while d * d <= n:
if n mod d == 0:
return false
inc d, step
step = 6 - step
result = true
 
iterator ascendingPrimes(): int =
 
# Yield one digit primes.
for n in [2, 3, 5, 7]:
yield n
 
# Yield other primes by increasing length and in ascending order.
type Item = tuple[val, lastDigit: int]
var items: seq[Item] = collect(for n in 1..9: (n, n))
for ndigits in 2..9:
var nextItems: seq[Item]
for item in items:
for newDigit in (item.lastDigit + 1)..9:
let newVal = 10 * item.val + newDigit
nextItems.add (val: newVal, lastDigit: newDigit)
if newVal.isPrime():
yield newVal
items = move(nextItems)
 
 
var rank = 0
for prime in ascendingPrimes():
inc rank
stdout.write ($prime).align(8)
stdout.write if rank mod 10 == 0: '\n' else: ' '
</syntaxhighlight>
{{out}}
<pre> 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
</pre>
 
=={{header|OCaml}}==
Line 1,290 ⟶ 1,591:
 
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl">#!/usr/bin/perl
<syntaxhighlight lang="perl">
 
use strict;
use strict; # https://rosettacode.org/wiki/Ascending_primes
use warnings;
use ntheory qw( 'is_prime )';
 
print join( '', map { sprintf "%10d", $_ } sort { $a <=> $b }
map { sprintf '%10d', $_ }
grep /./ && is_prime($_),
sort { $a <=> $b }
glob join '', map "{$_,}", 1 .. 9) =~ s/.{50}\K/\n/gr;</syntaxhighlight>
grep /./ && is_prime $_,
glob join '', map "{$_,}", 1..9
) =~ s/.{50}\K/\n/gr;
</syntaxhighlight>
{{out}}
<pre>
Line 1,490 ⟶ 1,795:
34679 123457 123479 124567 124679 125789 134789 145679 234589 235679
235789 245789 345679 345689 1234789 1235789 1245689 1456789 12356789 23456789
</pre>
 
=={{header|Prolog}}==
{{works with|swi-prolog}}© 2023<syntaxhighlight lang="prolog">
isPrime(2).
isPrime(N):-
between(3, inf, N),
N /\ 1 > 0, % odd
M is floor(sqrt(N)) - 1, % reverse 2*I+1
Max is M div 2,
forall(between(1, Max, I), N mod (2*I+1) > 0).
 
combi(0, _, Num, Num).
combi(N, [X|T], Acc, Num):-
N > 0,
N1 is N - 1,
Acc1 is Acc * 10 + X,
combi(N1, T, Acc1, Num).
combi(N, [_|T], Acc, Num):-
N > 0,
combi(N, T, Acc, Num).
 
ascPrimes(Num):-
between(1, 9, N),
combi(N, [1, 2, 3, 4, 5, 6, 7, 8, 9], 0, Num),
isPrime(Num).
 
showList(List):-
findnsols(10, DPrim, (member(DPrim, List), writef('%9r', [DPrim])), _),
nl,
fail.
showList(_).
do:-findall(DPrim, ascPrimes(DPrim), DList),
showList(DList).
</syntaxhighlight>
{{out}}
<pre>
?- do.
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
true.
</pre>
 
Line 1,996 ⟶ 2,351:
===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.
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
 
Line 2,021 ⟶ 2,375:
ascPrimes.addAll(higherPrimes)
System.print("There are %(ascPrimes.count) ascending primes, namely:")
for (chunk in Lst.chunks(ascPrimes, 10)) Fmt.printtprint("$8d", chunkascPrimes, 10)</syntaxhighlight>
 
{{out}}
Line 2,042 ⟶ 2,396:
 
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.
<syntaxhighlight lang="ecmascriptwren">import "./set" for Set
import "./math" for Int
import "./seq" for Lst
import "./fmt" for Fmt
 
Line 2,067 ⟶ 2,420:
ascPrimes.sort()
System.print("There are %(ascPrimes.count) ascending primes, namely:")
for (chunk in Lst.chunks(ascPrimes, 10)) Fmt.printtprint("$8s8d", chunkascPrimes, 10)</syntaxhighlight>
 
{{out}}
Achim
51

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/340270...355540"