Concatenate two primes is also prime
- Task
Find and show here when the concatenation of two primes (p1, p2) shown in base ten is also prime, where p1, p2 < 100
Go
<lang go>package main
import (
"fmt" "rcu" "sort"
)
func main() {
const LIMIT = 99 primes := rcu.Primes(LIMIT) rmap := make(map[int]bool) for _, p := range primes { for _, q := range primes { var pq int if q < 10 { pq = p*10 + q } else { pq = p*100 + q } if rcu.IsPrime(pq) { rmap[pq] = true } } } results := make([]int, len(rmap)) i := 0 for k := range rmap { results[i] = k i++ } sort.Ints(results) fmt.Println("Two primes under 100 concatenated together to form another prime:") for i, p := range results { fmt.Printf("%5s ", rcu.Commatize(p)) if (i+1)%10 == 0 { fmt.Println() } } fmt.Println("\n\nFound", len(results), "such concatenated primes.")
}</lang>
- Output:
Two primes under 100 concatenated together to form another prime: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1,117 1,123 1,129 1,153 1,171 1,319 1,361 1,367 1,373 1,723 1,741 1,747 1,753 1,759 1,783 1,789 1,913 1,931 1,973 1,979 1,997 2,311 2,341 2,347 2,371 2,383 2,389 2,917 2,953 2,971 3,119 3,137 3,167 3,719 3,761 3,767 3,779 3,797 4,111 4,129 4,153 4,159 4,337 4,373 4,397 4,723 4,729 4,759 4,783 4,789 5,323 5,347 5,923 5,953 6,113 6,131 6,143 6,173 6,197 6,719 6,737 6,761 6,779 7,129 7,159 7,331 7,919 7,937 8,311 8,317 8,329 8,353 8,389 8,923 8,929 8,941 8,971 9,719 9,743 9,767 Found 128 such concatenated primes.
Nim
<lang Nim>import strutils, sugar
func isPrime(n: Positive): bool =
if n == 1: return false if (n and 1) == 0: return n == 2 if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false if n mod (d + 2) == 0: return false inc d, 6 result = true
- List of primes.
const Primes = collect(newSeq, for n in 2..<100: (if n.isPrime: n))
var concatPrimes: set[0..9999] # Using a set to eliminate duplicates and avoid sort. for p1 in Primes:
for p2 in Primes: let n = p2 + p1 * (if p2 < 10: 10 else: 100) if n.isPrime: concatPrimes.incl n
echo "Found $# primes which are a concatenation of two primes below 100:".format(concatPrimes.len) var i = 1 for n in concatPrimes:
stdout.write ($n).align(4), if i mod 16 == 0: '\n' else: ' ' inc i</lang>
- Output:
Found 128 primes which are a concatenation of two primes below 100: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Concatenate_two_primes_is_also_prime use warnings; use ntheory qw( primes is_prime ); use List::Util qw( uniq );
my @primes = @{ primes(100) }; my @valid = uniq sort { $a <=> $b } grep is_prime($_),
map { my $prefix = $_; map "$prefix$_", @primes } @primes;
print @valid . " primes found\n\n@valid\n" =~ s/.{79}\K /\n/gr;</lang>
- Output:
128 primes found 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767
Raku
Inefficient, but for a limit of 100, who cares? <lang perl6>my @p = ^1e2 .grep: *.is-prime;
say display ( @p X~ @p ).grep( *.is-prime ).unique.sort( +* );
sub display ($list, :$cols = 10, :$fmt = '%6d', :$title = "{+$list} matching:\n") {
cache $list; $title ~ $list.batch($cols)».fmt($fmt).join: "\n"
}</lang>
- Output:
128 matching: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767
REXX
<lang rexx>/*REXX pgm finds & displays base ten primes P1 & P2, when concatenated, is also a prime.*/ parse arg hip cols . /*obtain optional arguments from the CL*/ if hip== | hip=="," then hip= 100 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ title= ' concatenation of two primes (P1, P2) in base ten that results in a prime, ' ,
" where P1 & P2 are < " commas(hip)
w= 10 /*width of a number in any column. */ if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') a.= 0 /*array of "2cat" primes */
do j=1 for ##; p1= @.j /*search for "cat2" primes. */ do k=1 for ##; p2= @.k /*search through allowable primes. */ cat2= p1 || p2 /*create a concatenated prime (base 10)*/ if !.cat2 then a.cat2= 1 /*flag it as being a "2cat" prime. */ end /*k*/ /* [↑] forgoes the need for sorting. */ end /*j*/
found= 0; idx= 1 /*initialize # of primes found; IDX. */ $=; do n=1 by 2 for hip**2%2 /*search for odd "cat2" primes. */
if \a.n then iterate /*search through allowable primes. */ found= found + 1 /*bump the number of primes found. */ if cols<=0 then iterate /*Build the list (to be shown later)? */ c= commas(n) /*maybe add commas to the number. */ $= $ right(c, max(w, length(c) ) ) /*add a prime ──► $ list, allow big #*/ if found//cols\==0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*n*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') say say 'Found ' commas(found) title exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " semaphores. */ #= 5; sq.#= @.#**2 /*the square of the highest low prime. */ do j=@.#+2 by 2 to hip**2-1 /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/ if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; sq.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ if j<hip then ##= # /*find a shortcut for the 1st DO loop. */ end /*j*/; return</lang>
- output when using the default inputs:
index │ concatenation of two primes (P1, P2) in base ten that results in a prime, where P1 & P2 are < 100 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 23 37 53 73 113 137 173 193 197 211 11 │ 223 229 233 241 271 283 293 311 313 317 21 │ 331 337 347 353 359 367 373 379 383 389 31 │ 397 433 523 541 547 571 593 613 617 673 41 │ 677 719 733 743 761 773 797 977 1,117 1,123 51 │ 1,129 1,153 1,171 1,319 1,361 1,367 1,373 1,723 1,741 1,747 61 │ 1,753 1,759 1,783 1,789 1,913 1,931 1,973 1,979 1,997 2,311 71 │ 2,341 2,347 2,371 2,383 2,389 2,917 2,953 2,971 3,119 3,137 81 │ 3,167 3,719 3,761 3,767 3,779 3,797 4,111 4,129 4,153 4,159 91 │ 4,337 4,373 4,397 4,723 4,729 4,759 4,783 4,789 5,323 5,347 101 │ 5,923 5,953 6,113 6,131 6,143 6,173 6,197 6,719 6,737 6,761 111 │ 6,779 7,129 7,159 7,331 7,919 7,937 8,311 8,317 8,329 8,353 121 │ 8,389 8,923 8,929 8,941 8,971 9,719 9,743 9,767 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 128 concatenation of two primes (P1, P2) in base ten that results in a prime, where P1 & P2 are < 100
Ring
<lang ring> load "stdlib.ring" see "working..." + nl see "Concatenate two primes is also prime:" + nl row = 0 prime = []
for n = 1 to 100
for m = 1 to 100 ps1 = string(n) ps2 = string(m) ps12 = ps1 + ps2 ps21 = ps2 + ps1 p1 = number(ps12) p2 = number(ps21) if isprime(n) and isprime(m) if isprime(p1) pf = find(prime,p1) if pf < 1 add(prime,p1) ok ok if isprime(p2) pf = find(prime,p2) if pf < 1 add(prime,p2) ok ok ok next
next
prime = sort(prime) for n = 1 to len(prime)
row++ see "" + prime[n] + " " if row%10 = 0 see nl ok
next
see nl + "Found " + row + " prime numbers" + nl see "done..." + nl </lang>
- Output:
working... Concatenate two primes is also prime: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1117 1123 1129 1153 1171 1319 1361 1367 1373 1723 1741 1747 1753 1759 1783 1789 1913 1931 1973 1979 1997 2311 2341 2347 2371 2383 2389 2917 2953 2971 3119 3137 3167 3719 3761 3767 3779 3797 4111 4129 4153 4159 4337 4373 4397 4723 4729 4759 4783 4789 5323 5347 5923 5953 6113 6131 6143 6173 6197 6719 6737 6761 6779 7129 7159 7331 7919 7937 8311 8317 8329 8353 8389 8923 8929 8941 8971 9719 9743 9767 Found 128 prime numbers done...
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt import "/seq" for Lst
var limit = 99 var primes = Int.primeSieve(limit) var results = [] for (p in primes) {
for (q in primes) { var pq = (q < 10) ? p*10 + q : p*100 + q if (Int.isPrime(pq)) results.add(pq) }
} results = Lst.distinct(results) results.sort() System.print("Two primes under 100 concatenated together to form another prime:") for (chunk in Lst.chunks(results, 10)) Fmt.print("$,6d", chunk) System.print("\nFound %(results.count) such concatenated primes.")</lang>
- Output:
Two primes under 100 concatenated together to form another prime: 23 37 53 73 113 137 173 193 197 211 223 229 233 241 271 283 293 311 313 317 331 337 347 353 359 367 373 379 383 389 397 433 523 541 547 571 593 613 617 673 677 719 733 743 761 773 797 977 1,117 1,123 1,129 1,153 1,171 1,319 1,361 1,367 1,373 1,723 1,741 1,747 1,753 1,759 1,783 1,789 1,913 1,931 1,973 1,979 1,997 2,311 2,341 2,347 2,371 2,383 2,389 2,917 2,953 2,971 3,119 3,137 3,167 3,719 3,761 3,767 3,779 3,797 4,111 4,129 4,153 4,159 4,337 4,373 4,397 4,723 4,729 4,759 4,783 4,789 5,323 5,347 5,923 5,953 6,113 6,131 6,143 6,173 6,197 6,719 6,737 6,761 6,779 7,129 7,159 7,331 7,919 7,937 8,311 8,317 8,329 8,353 8,389 8,923 8,929 8,941 8,971 9,719 9,743 9,767 Found 128 such concatenated primes.