Primes with digits in nondecreasing order
- Task
Find n primes with digits in non-decreasing order, where n < 1000
ALGOL 68
<lang algol68>BEGIN # find primes where the digits are non-descending #
INT max number = 1000; # sieve the primes to max number # [ 1 : max number ]BOOL prime; prime[ 1 ] := FALSE; prime[ 2 ] := TRUE; FOR i FROM 3 BY 2 TO max number DO prime[ i ] := TRUE OD; FOR i FROM 4 BY 2 TO max number DO prime[ i ] := FALSE OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( max number ) DO IF prime[ i ] THEN FOR s FROM i * i BY i + i TO max number DO prime[ s ] := FALSE OD FI OD; # we can easily generate candidate numbers with a few nested loops # INT p count := 0; # apart from 1 digit primes, the final digit can only be 1, 3, 7 or 9 # # however we don't optimise that here # FOR h FROM 0 TO 9 DO FOR i FROM h TO 9 DO INT hi = ( h * 10 ) + i; FOR j FROM i TO 9 DO INT hij = ( 10 * hi ) + j; FOR k FROM IF j = 0 THEN 1 ELSE j FI TO 9 WHILE INT hijk = ( hij * 10 ) + k; hijk <= max number DO IF prime[ hijk ] THEN p count +:= 1; print( ( " ", whole( hijk, -6 ) ) ); IF p count MOD 12 = 0 THEN print( ( newline ) ) FI FI OD # k # OD # j # OD # i # OD # h # ; print( ( newline , newline , "Found " , whole( p count, 0 ) , " non-descending primes up to " , whole( max number, 0 ) , newline ) )
END</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Found 50 non-descending primes up to 1000
AWK
<lang AWK>
- syntax: GAWK -f PRIMES_WITH_DIGITS_IN_NONDECREASING_ORDER.AWK
BEGIN {
start = 1 stop = 1000 for (i=start; i<=stop; i++) { if (is_prime(i)) { flag = 1 for (j=1; j<length(i); j++) { if (substr(i,j,1) > substr(i,j+1,1)) { flag = 0 } } if (flag == 1) { printf("%4d%1s",i,++count%10?"":"\n") } } } printf("\nPrimes with digits in nondecreasing order %d-%d: %d\n",start,stop,count) exit(0)
} function is_prime(x, i) {
if (x <= 1) { return(0) } for (i=2; i<=int(sqrt(x)); i++) { if (x % i == 0) { return(0) } } return(1)
} </lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Primes with digits in nondecreasing order 1-1000: 50
C#
The chars array explicitly enforces the case order, not relying on the language's idea of what letters are before or after each other. <lang csharp>using System.Linq; using System.Collections.Generic; using static System.Console; using static System.Math;
class Program {
static int ba; static string chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// convert an int into a string using the current ba static string from10(int b) { string res = ""; int re; while (b > 0) { b = DivRem(b, ba, out re); res = chars[(byte)re] + res; } return res; }
// parse a string into an int, using current ba (not used here) static int to10(string s) { int res = 0; foreach (char i in s) res = res * ba + chars.IndexOf(i); return res; }
// note: comparing the index of the chars instead of the chars themsleves, which avoids case issues static bool nd(string s) { if (s.Length < 2) return true; char l = s[0]; for (int i = 1; i < s.Length; i++) if (chars.IndexOf(l) > chars.IndexOf(s[i])) return false; else l = s[i] ; return true; }
static void Main(string[] args) { int c, lim = 1000; string s; foreach (var b in new List<int>{ 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 17, 27, 31, 62 }) { ba = b; c = 0; foreach (var a in PG.Primes(lim)) if (nd(s = from10(a))) Write("{0,4} {1}", s, ++c % 20 == 0 ? "\n" : ""); WriteLine("\nBase {0}: found {1} non-decreasing primes under {2:n0}\n", b, c, from10(lim)); } } }
class PG { public static IEnumerable<int> Primes(int lim) {
var flags = new bool[lim + 1]; int j; yield return 2; for (j = 4; j <= lim; j += 2) flags[j] = true; j = 3; for (int d = 8, sq = 9; sq <= lim; j += 2, sq += d += 8) if (!flags[j]) { yield return j; for (int k = sq, i = j << 1; k <= lim; k += i) flags[k] = true; } for (; j <= lim; j += 2) if (!flags[j]) yield return j; } }</lang>
- Output:
11 111 11111 1111111 Base 2: found 4 non-decreasing primes under 1111101000 2 12 111 122 1112 1222 Base 3: found 6 non-decreasing primes under 1101001 2 3 11 13 23 113 133 223 233 1223 1333 2333 11123 11233 11333 12233 22223 Base 4: found 17 non-decreasing primes under 33220 2 3 12 23 34 111 122 133 1112 1123 1233 1244 2223 2344 3444 11122 12222 Base 5: found 17 non-decreasing primes under 13000 2 3 5 11 15 25 35 45 111 115 125 135 155 225 245 255 335 345 445 455 1115 1125 1145 1235 1245 1335 1345 1355 1445 1555 2225 2335 2345 2555 3445 3455 3555 Base 6: found 37 non-decreasing primes under 4344 2 3 5 14 16 23 25 56 113 115 124 133 146 155 166 245 256 335 344 346 445 566 1112 1123 1136 1156 1222 1226 1235 1345 1444 1466 2234 2236 2333 2335 2366 2555 Base 7: found 38 non-decreasing primes under 2626 2 3 5 7 13 15 23 27 35 37 45 57 111 117 123 145 147 155 177 225 227 235 247 255 277 337 345 357 445 467 557 577 667 1113 1127 1137 1145 1167 1223 1225 1245 1335 1347 1357 1467 1555 1567 Base 8: found 47 non-decreasing primes under 1750 2 3 5 7 12 14 18 25 34 45 47 58 67 78 117 122 124 128 135 155 177 234 238 267 278 337 344 355 377 447 557 568 667 678 788 1112 1114 1118 1147 1158 1178 1222 1255 1268 1288 Base 9: found 45 non-decreasing primes under 1331 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Base 10: found 50 non-decreasing primes under 1000 2 3 5 7 B D 11 13 17 1D 1F 25 29 2B 2F 35 3B 3D 47 49 4F 59 67 6B 6D 7F 89 8B 9D AD BF DF EF 115 119 11B 125 133 137 139 13D 14B 15B 15D 167 16F 17B 17F 18D 199 1AF 1BB 1CD 1CF 1DF 223 22D 233 239 23B 24B 257 259 25F 269 26B 277 28D 2AB 2BD 2CF 2DD 2EF 335 337 33B 33D 347 355 359 35B 35F 36D 377 38B 38F 3AD 3DF Base 16: found 88 non-decreasing primes under 3E8 2 3 5 7 B D 12 16 1C 1E 23 27 29 2D 38 3A 3G 45 4B 4F 5C 5G 67 6B 78 7C 8D 8F 9A 9E AB BC FG 111 115 117 11B 128 12E 137 139 13D 14A 14G 155 159 15F 166 16A 17B 17D 188 18E 19F 1BB 1BF 1CG 1DD 1EE 1GG 225 227 23C 23E 247 24D 24F 25A 25E 26B 27C 28D 29C 2AD 2CF 33B 346 34C 35F 368 36E 37B Base 17: found 82 non-decreasing primes under 37E 2 3 5 7 B D H J N 12 14 1A 1E 1G 1K 1Q 25 27 2D 2H 2J 2P 38 3G 3K 3M 3Q 45 4J 4N 5E 5G 5M 6B 6H 6J 78 7A 7M 8B 8D 8H 8N 8P 9E 9K 9Q AB AD AN BE BG BK CD CN CP DG DM EJ EN FG FQ GH GP HK IN KN LQ MN MP NQ OP PQ 111 115 11D 11H 124 12E 12Q 13B 13D 13H 13J 14G 14K 14M 14Q 15D 15H 15J 15N 16G 16K 17B 17J 17N 188 18M 18Q 19B 19J 19P Base 27: found 103 non-decreasing primes under 1A1 2 3 5 7 B D H J N T 16 1A 1C 1G 1M 1S 1U 25 29 2B 2H 2L 2R 34 38 3A 3E 3G 3K 47 4D 4F 4P 4R 58 5C 5I 5O 5Q 67 6B 6D 6P 7A 7C 7G 7M 7O 89 8F 8L 8N 8T 9E 9S AL AR BC BI BQ CH CP CT DG DI DS DU EF EN ER ET FM FQ GP GR HK HU IJ IT JO JS JU KL KN KR LM LQ MR NQ NU OP OT TU 115 Base 31: found 94 non-decreasing primes under 118 2 3 5 7 B D H J N T V b f h l r x z 15 19 1B 1H 1L 1R 1Z 1d 1f 1j 1l 1p 23 27 2D 2F 2P 2R 2X 2d 2h 2n 2t 2v 35 37 3B 3D 3P 3b 3f 3h 3l 3r 3t 49 4F 4L 4N 4T 4X 4Z 4j 4x 57 5L 5R 5b 5d 5h 5n 5v 67 6B 6H 6P 6T 6b 6l 6n 6x 6z 79 7F 7N 7R 7T 7X 7j 7r 7v 8D 8P 8R 8j 8p 8z 9B 9D 9J 9T 9Z 9f 9h 9n 9t 9x 9z AB AL AN AR AX Ad Af Ar Av BJ BR Bb Bj Bp Bv Bz CD CH CP CT Ch Cr DF DH DL DN DX Dl Dp Dr Dv EF EJ Ed Eh Ep Ez FH FN Fb Ff Fl Fr Fz Base 62: found 150 non-decreasing primes under G8
Factor
<lang factor>USING: grouping lists lists.lazy math math.primes.lists present prettyprint ;
lprimes [ present [ <= ] monotonic? ] lfilter [ 1000 < ] lwhile [ . ] leach</lang>
- Output:
2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677
Julia
Note for the case-sensitive digits base 62 example: Julia defaults to 'A' < 'a' in sorting. So Aa is in order, but aA is not nondecreasing. <lang julia>using Primes
const range = 2:999
for base in [2:10...;[16, 17, 27, 31, 62]]
primes = filter(n -> isprime(n) && issorted(digits(n, base=base), rev=true), range) println("\nBase $base: ", length(primes), " non-descending primes between 1 and ", string(last(primes), base=base), ":") foreach(p -> print(lpad(string(p[2], base=base), 5), p[1] % 16 == 0 ? "\n" : ""), enumerate(primes))
end
</lang>
- Output:
Base 2: 4 non-descending primes between 1 and 1111111: 11 111111111111111 Base 3: 6 non-descending primes between 1 and 1222: 2 12 111 122 1112 1222 Base 4: 17 non-descending primes between 1 and 22223: 2 3 11 13 23 113 133 223 233 1223 1333 233311123112331133312233 22223 Base 5: 17 non-descending primes between 1 and 12222: 2 3 12 23 34 111 122 133 1112 1123 1233 1244 2223 2344 344411122 12222 Base 6: 37 non-descending primes between 1 and 3555: 2 3 5 11 15 25 35 45 111 115 125 135 155 225 245 255 335 345 445 455 1115 1125 1145 1235 1245 1335 1345 1355 1445 1555 2225 2335 2345 2555 3445 3455 3555 Base 7: 38 non-descending primes between 1 and 2555: 2 3 5 14 16 23 25 56 113 115 124 133 146 155 166 245 256 335 344 346 445 566 1112 1123 1136 1156 1222 1226 1235 1345 1444 1466 2234 2236 2333 2335 2366 2555 Base 8: 47 non-descending primes between 1 and 1567: 2 3 5 7 13 15 23 27 35 37 45 57 111 117 123 145 147 155 177 225 227 235 247 255 277 337 345 357 445 467 557 577 667 1113 1127 1137 1145 1167 1223 1225 1245 1335 1347 1357 1467 1555 1567 Base 9: 45 non-descending primes between 1 and 1288: 2 3 5 7 12 14 18 25 34 45 47 58 67 78 117 122 124 128 135 155 177 234 238 267 278 337 344 355 377 447 557 568 667 678 788 1112 1114 1118 1147 1158 1178 1222 1255 1268 1288 Base 10: 50 non-descending primes between 1 and 677: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Base 16: 88 non-descending primes between 1 and 3df: 2 3 5 7 b d 11 13 17 1d 1f 25 29 2b 2f 35 3b 3d 47 49 4f 59 67 6b 6d 7f 89 8b 9d ad bf df ef 115 119 11b 125 133 137 139 13d 14b 15b 15d 167 16f 17b 17f 18d 199 1af 1bb 1cd 1cf 1df 223 22d 233 239 23b 24b 257 259 25f 269 26b 277 28d 2ab 2bd 2cf 2dd 2ef 335 337 33b 33d 347 355 359 35b 35f 36d 377 38b 38f 3ad 3df Base 17: 82 non-descending primes between 1 and 37b: 2 3 5 7 b d 12 16 1c 1e 23 27 29 2d 38 3a 3g 45 4b 4f 5c 5g 67 6b 78 7c 8d 8f 9a 9e ab bc fg 111 115 117 11b 128 12e 137 139 13d 14a 14g 155 159 15f 166 16a 17b 17d 188 18e 19f 1bb 1bf 1cg 1dd 1ee 1gg 225 227 23c 23e 247 24d 24f 25a 25e 26b 27c 28d 29c 2ad 2cf 33b 346 34c 35f 368 36e 37b Base 27: 103 non-descending primes between 1 and 19p: 2 3 5 7 b d h j n 12 14 1a 1e 1g 1k 1q 25 27 2d 2h 2j 2p 38 3g 3k 3m 3q 45 4j 4n 5e 5g 5m 6b 6h 6j 78 7a 7m 8b 8d 8h 8n 8p 9e 9k 9q ab ad an be bg bk cd cn cp dg dm ej en fg fq gh gp hk in kn lq mn mp nq op pq 111 115 11d 11h 124 12e 12q 13b 13d 13h 13j 14g 14k 14m 14q 15d 15h 15j 15n 16g 16k 17b 17j 17n 188 18m 18q 19b 19j 19p Base 31: 94 non-descending primes between 1 and 115: 2 3 5 7 b d h j n t 16 1a 1c 1g 1m 1s 1u 25 29 2b 2h 2l 2r 34 38 3a 3e 3g 3k 47 4d 4f 4p 4r 58 5c 5i 5o 5q 67 6b 6d 6p 7a 7c 7g 7m 7o 89 8f 8l 8n 8t 9e 9s al ar bc bi bq ch cp ct dg di ds du ef en er et fm fq gp gr hk hu ij it jo js ju kl kn kr lm lq mr nq nu op ot tu 115 Base 62: 150 non-descending primes between 1 and Fz: 2 3 5 7 B D H J N T V b f h l r x z 15 19 1B 1H 1L 1R 1Z 1d 1f 1j 1l 1p 23 27 2D 2F 2P 2R 2X 2d 2h 2n 2t 2v 35 37 3B 3D 3P 3b 3f 3h 3l 3r 3t 49 4F 4L 4N 4T 4X 4Z 4j 4x 57 5L 5R 5b 5d 5h 5n 5v 67 6B 6H 6P 6T 6b 6l 6n 6x 6z 79 7F 7N 7R 7T 7X 7j 7r 7v 8D 8P 8R 8j 8p 8z 9B 9D 9J 9T 9Z 9f 9h 9n 9t 9x 9z AB AL AN AR AX Ad Af Ar Av BJ BR Bb Bj Bp Bv Bz CD CH CP CT Ch Cr DF DH DL DN DX Dl Dp Dr Dv EF EJ Ed Eh Ep Ez FH FN Fb Ff Fl Fr Fz
Phix
function nd(string s) return s=sort(s) end function sequence res = filter(apply(true,sprintf,{{"%d"},get_primes_le(1000)}),nd) printf(1,"%d non-decreasing primes < 1,000: %s\n",{length(res),join(shorten(res,"",5))})
- Output:
50 non-decreasing primes < 1,000: 2 3 5 7 11 ... 557 569 577 599 677
Raku
<lang perl6>my $range = ^1000;
for flat 2..10, 17, 27, 31 -> $base {
say "\nBase $base: {+$_} non-decending primes between $range.minmax.map( *.base: $base ).join(' and '):\n{ .batch(20)».fmt("%{.tail.chars}s").join: "\n" }" given $range.grep( *.is-prime ).map( *.base: $base ).grep: { [le] .comb }
}</lang>
- Output:
Base 2: 4 non-decending primes between 0 and 1111100111: 11 111 11111 1111111 Base 3: 6 non-decending primes between 0 and 1101000: 2 12 111 122 1112 1222 Base 4: 17 non-decending primes between 0 and 33213: 2 3 11 13 23 113 133 223 233 1223 1333 2333 11123 11233 11333 12233 22223 Base 5: 17 non-decending primes between 0 and 12444: 2 3 12 23 34 111 122 133 1112 1123 1233 1244 2223 2344 3444 11122 12222 Base 6: 37 non-decending primes between 0 and 4343: 2 3 5 11 15 25 35 45 111 115 125 135 155 225 245 255 335 345 445 455 1115 1125 1145 1235 1245 1335 1345 1355 1445 1555 2225 2335 2345 2555 3445 3455 3555 Base 7: 38 non-decending primes between 0 and 2625: 2 3 5 14 16 23 25 56 113 115 124 133 146 155 166 245 256 335 344 346 445 566 1112 1123 1136 1156 1222 1226 1235 1345 1444 1466 2234 2236 2333 2335 2366 2555 Base 8: 47 non-decending primes between 0 and 1747: 2 3 5 7 13 15 23 27 35 37 45 57 111 117 123 145 147 155 177 225 227 235 247 255 277 337 345 357 445 467 557 577 667 1113 1127 1137 1145 1167 1223 1225 1245 1335 1347 1357 1467 1555 1567 Base 9: 45 non-decending primes between 0 and 1330: 2 3 5 7 12 14 18 25 34 45 47 58 67 78 117 122 124 128 135 155 177 234 238 267 278 337 344 355 377 447 557 568 667 678 788 1112 1114 1118 1147 1158 1178 1222 1255 1268 1288 Base 10: 50 non-decending primes between 0 and 999: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Base 17: 82 non-decending primes between 0 and 37D: 2 3 5 7 B D 12 16 1C 1E 23 27 29 2D 38 3A 3G 45 4B 4F 5C 5G 67 6B 78 7C 8D 8F 9A 9E AB BC FG 111 115 117 11B 128 12E 137 139 13D 14A 14G 155 159 15F 166 16A 17B 17D 188 18E 19F 1BB 1BF 1CG 1DD 1EE 1GG 225 227 23C 23E 247 24D 24F 25A 25E 26B 27C 28D 29C 2AD 2CF 33B 346 34C 35F 368 36E 37B Base 27: 103 non-decending primes between 0 and 1A0: 2 3 5 7 B D H J N 12 14 1A 1E 1G 1K 1Q 25 27 2D 2H 2J 2P 38 3G 3K 3M 3Q 45 4J 4N 5E 5G 5M 6B 6H 6J 78 7A 7M 8B 8D 8H 8N 8P 9E 9K 9Q AB AD AN BE BG BK CD CN CP DG DM EJ EN FG FQ GH GP HK IN KN LQ MN MP NQ OP PQ 111 115 11D 11H 124 12E 12Q 13B 13D 13H 13J 14G 14K 14M 14Q 15D 15H 15J 15N 16G 16K 17B 17J 17N 188 18M 18Q 19B 19J 19P Base 31: 94 non-decending primes between 0 and 117: 2 3 5 7 B D H J N T 16 1A 1C 1G 1M 1S 1U 25 29 2B 2H 2L 2R 34 38 3A 3E 3G 3K 47 4D 4F 4P 4R 58 5C 5I 5O 5Q 67 6B 6D 6P 7A 7C 7G 7M 7O 89 8F 8L 8N 8T 9E 9S AL AR BC BI BQ CH CP CT DG DI DS DU EF EN ER ET FM FQ GP GR HK HU IJ IT JO JS JU KL KN KR LM LQ MR NQ NU OP OT TU 115
REXX
<lang rexx>/*REXX program finds & displays primes whose decimal digits are in non─decreasing order.*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 1000 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */
@ndcps= ' primes whose decimal digits are in non─decreasing order that' , 'are < ' commas(hi)
if cols>0 then say ' index │'center(@ndcps, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') ndcps= 0; idx= 1 /*initialize # of non─decreasing primes*/ $= /*a list of non─decreasing digit primes*/
do j=1 while @.j<hi; p= @.j /*examine the primes within the range. */ do k=1 for length(p)-1 /*validate that it meets specifications*/ if substr(p, k, 1) > substr(p, k+1, 1) then iterate j /*compare dig with next.*/ end /*k*/ ndcps= ndcps + 1 /*bump number of non─decreasing primes.*/ if cols==0 then iterate /*Build the list (to be shown later)? */ c= commas(p) /*maybe add commas to the number. */ $= $ right(c, max(w, length(c) ) ) /*add a prime ──► list, allow big nums.*/ if ndcps//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'Found ' commas(ndcps) @ndcps exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7 /*define some low primes. */
#= 3; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 to hi /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ /* [↑] the above five lines saves time*/ do k=4 while s.k<=j /* [↓] divide by the known odd primes.*/ if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; s.#= j*j /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
index │ primes whose decimal digits are in non─decreasing order that are < 1,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 2 3 5 7 11 13 17 19 23 29 11 │ 37 47 59 67 79 89 113 127 137 139 21 │ 149 157 167 179 199 223 227 229 233 239 31 │ 257 269 277 337 347 349 359 367 379 389 41 │ 449 457 467 479 499 557 569 577 599 677 Found 50 primes whose decimal digits are in non─decreasing order that are < 1,000
Ring
<lang ring>load "stdlib.ring"
? "working..."
c = 0 limit = 1000
? "Primes under " + limit + " with digits in nondecreasing order:"
for n = 1 to limit
flag = 1 strn = string(n) if isprime(n) for m = 1 to len(strn) - 1 if strn[m] > strn[m + 1] flag = 0 exit ok next if flag = 1 see sf(n, 4) + " " c++ if c % 10 = 0 see nl ok ok ok
next
? nl + "Found " + c + " base 10 primes with digits in nondecreasing order" ? "done..."
- a very plain string formatter, intended to even up columnar outputs
def sf x, y
s = string(x) l = len(s) if l > y y = l ok return substr(" ", 11 - y + l) + s</lang>
- Output:
working... Primes under 1000 with digits in nondecreasing order: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 Found 50 base 10 primes with digits in nondecreasing order done...
Visual Basic .NET
<lang vbnet>Imports System.Linq Imports System.Collections.Generic Imports System.Console Imports System.Math
Module Module1
Dim ba As Integer Dim chars As String = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
Iterator Function Primes(ByVal lim As Integer) As IEnumerable(Of Integer) Dim flags(lim) As Boolean, j As Integer : Yield 2 For j = 4 To lim Step 2 : flags(j) = True : Next : j = 3 Dim d As Integer = 8, sq As Integer = 9 While sq <= lim If Not flags(j) Then Yield j : Dim i As Integer = j << 1 For k As Integer = sq To lim step i : flags(k) = True : Next End If j += 2 : d += 8 : sq += d : End While While j <= lim If Not flags(j) Then Yield j j += 2 : End While End Function
' convert an int into a string using the current ba Function from10(ByVal b As Integer) As String Dim res As String = "", re As Integer While b > 0 : b = DivRem(b, ba, re) : res = chars(CByte(re)) & res : End While : Return res End Function
' parse a string into an int, using current ba (not used here) Function to10(ByVal s As String) As Integer Dim res As Integer = 0 For Each i As Char In s : res = res * ba + chars.IndexOf(i) : Next : Return res End Function
' note: comparing the index of the chars instead of the chars themsleves, which avoids case issues Function nd(ByVal s As String) As Boolean If s.Length < 2 Then Return True Dim l As Char = s(0) For i As Integer = 1 To s.Length - 1 If chars.IndexOf(l) > chars.IndexOf(s(i)) Then Return False Else l = s(i) Next : Return True End Function
Sub Main(ByVal args As String()) Dim c As Integer, lim As Integer = 1000, s As String For Each b As Integer In New List(Of Integer) From { 2, 3, 4, 5, 6, 7, 8, 9, 10, 16, 17, 27, 31, 62 } ba = b : c = 0 : For Each a As Integer In Primes(lim) s = from10(a) : If nd(s) Then c += 1 : Write("{0,4} {1}", s, If(c Mod 20 = 0, vbLf, "")) Next WriteLine(vbLf & "Base {0}: found {1} non-decreasing primes under {2:n0}" & vbLf, b, c, from10(lim)) Next End Sub
End Module</lang>
- Output:
Same as C#.
Wren
<lang ecmascript>import "/math" for Int import "/seq" for Lst import "/fmt" for Fmt
var nonDescending = Fn.new { |p|
var digits = [] while (p > 0) { digits.add(p % 10) p = (p/10).floor } for (i in 0...digits.count-1) { if (digits[i+1] > digits[i]) return false } return true
}
var primes = Int.primeSieve(999) var nonDesc = [] for (p in primes) if (nonDescending.call(p)) nonDesc.add(p) System.print("Primes below 1,000 with digits in non-decreasing order:") for (chunk in Lst.chunks(nonDesc, 10)) Fmt.print("$3d", chunk) System.print("\n%(nonDesc.count) such primes found.")</lang>
- Output:
Primes below 1,000 with digits in non-decreasing order: 2 3 5 7 11 13 17 19 23 29 37 47 59 67 79 89 113 127 137 139 149 157 167 179 199 223 227 229 233 239 257 269 277 337 347 349 359 367 379 389 449 457 467 479 499 557 569 577 599 677 50 such primes found.