Special neighbor primes: Difference between revisions
(Add Factor) |
(→{{header|REXX}}: changed program to use neighbor primes.) |
||
Line 198: | Line 198: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
⚫ | |||
The output list is displayed in numerical order by prime '''P''' and then by prime '''Q'''. |
|||
⚫ | |||
parse arg hi cols . /*obtain optional argument from the CL.*/ |
parse arg hi cols . /*obtain optional argument from the CL.*/ |
||
if hi=='' | hi=="," then hi= 100 /*Not specified? Then use the default.*/ |
if hi=='' | hi=="," then hi= 100 /*Not specified? Then use the default.*/ |
||
if cols=='' | cols=="," then cols= 5 /* " " " " " " */ |
if cols=='' | cols=="," then cols= 5 /* " " " " " " */ |
||
call genP hi /*build semaphore array for low primes.*/ |
call genP hi /*build semaphore array for low primes.*/ |
||
do p=1 while @.p<hi |
|||
⚫ | |||
end /*p*/; lim= p-1; q= p+1 /*set LIM to prime for P; calc. 2nd HI.*/ |
|||
#m= # - 1 |
|||
⚫ | |||
w= 20 /*width of a number in any column. */ |
w= 20 /*width of a number in any column. */ |
||
title= ' special neighbor primes: |
title= ' special neighbor primes: P1, P2, P1+P2-1 are primes, and P1 and P2 < ' , |
||
⚫ | |||
⚫ | |||
if cols>0 then say ' |
if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) |
||
⚫ | |||
found= 0; idx= 1 /*init. # special neighbor primes & IDX*/ |
|||
found= 0; idx= 1 /*initialize # neighbor primes & index.*/ |
|||
$= /*a list of neighbor primes (so far).*/ |
|||
do j=1 to lim; jp= j+1; q= @.jp /*look for neighbor primes within range*/ |
|||
y= @.j + q - 1; if \!.y then iterate /*is X also a prime? No, then skip it.*/ |
|||
found= found + 1 /*bump the number of neighbor primes. */ |
|||
if cols==0 then iterate /*Build the list (to be shown later)? */ |
|||
$= $ right( @.j','q"──►"y, w) /*add neighbor prime ──► the $ list. */ |
|||
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*/ |
|||
⚫ | |||
idx= idx + cols /*bump the index count for the output*/ |
|||
⚫ | |||
end /*j*/ |
|||
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ |
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ |
||
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') |
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─') |
||
say |
say |
||
say 'Found ' commas(found) title |
say 'Found ' commas(found) title |
||
Line 236: | Line 235: | ||
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ |
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ |
||
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ |
!.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ |
||
#=5; |
#=5; s.#= @.# **2 /*number of primes so far; prime². */ |
||
/* [↓] generate more primes ≤ high.*/ |
/* [↓] generate more primes ≤ high.*/ |
||
do j=@.#+2 by 2 to limit /*find odd primes from here on. */ |
do j=@.#+2 by 2 to limit /*find odd primes from here on. */ |
||
parse var |
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? */ |
|||
/* [↑] the above 3 lines saves time.*/ |
|||
do k=5 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; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ |
|||
end /*j*/; return</lang> |
|||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
index │ |
index │ special neighbor primes: P1, P2, P1+P2-1 are primes, and P1 and P2 < 100 |
||
───────┼────────────────────────────────────────────────────────────────────────────────────────────────────────── |
───────┼────────────────────────────────────────────────────────────────────────────────────────────────────────── |
||
1 │ 3,5──►7 |
1 │ 3,5──►7 5,7──►11 7,11──►17 11,13──►23 13,17──►29 |
||
6 │ |
6 │ 19,23──►41 29,31──►59 31,37──►67 41,43──►83 43,47──►89 |
||
11 │ |
11 │ 61,67──►127 67,71──►137 73,79──►151 |
||
⚫ | |||
21 │ 7,37──►43 7,41──►47 7,47──►53 7,53──►59 7,61──►67 |
|||
26 │ 7,67──►73 7,73──►79 7,83──►89 7,97──►103 11,13──►23 |
|||
31 │ 11,19──►29 11,31──►41 11,37──►47 11,43──►53 11,61──►71 |
|||
36 │ 11,73──►83 11,79──►89 11,97──►107 13,17──►29 13,19──►31 |
|||
41 │ 13,29──►41 13,31──►43 13,41──►53 13,47──►59 13,59──►71 |
|||
46 │ 13,61──►73 13,67──►79 13,71──►83 13,89──►101 13,97──►109 |
|||
51 │ 17,31──►47 17,37──►53 17,43──►59 17,67──►83 17,73──►89 |
|||
56 │ 17,97──►113 19,23──►41 19,29──►47 19,41──►59 19,43──►61 |
|||
61 │ 19,53──►71 19,61──►79 19,71──►89 19,79──►97 19,83──►101 |
|||
66 │ 19,89──►107 23,31──►53 23,37──►59 23,61──►83 23,67──►89 |
|||
71 │ 23,79──►101 29,31──►59 29,43──►71 29,61──►89 29,73──►101 |
|||
76 │ 29,79──►107 31,37──►67 31,41──►71 31,43──►73 31,53──►83 |
|||
81 │ 31,59──►89 31,67──►97 31,71──►101 31,73──►103 31,79──►109 |
|||
86 │ 31,83──►113 31,97──►127 37,43──►79 37,47──►83 37,53──►89 |
|||
91 │ 37,61──►97 37,67──►103 37,71──►107 37,73──►109 41,43──►83 |
|||
96 │ 41,61──►101 41,67──►107 41,73──►113 41,97──►137 43,47──►89 |
|||
101 │ 43,59──►101 43,61──►103 43,67──►109 43,71──►113 43,89──►131 |
|||
106 │ 43,97──►139 47,61──►107 47,67──►113 53,61──►113 53,79──►131 |
|||
111 │ 53,97──►149 59,73──►131 59,79──►137 61,67──►127 61,71──►131 |
|||
116 │ 61,79──►139 61,89──►149 61,97──►157 67,71──►137 67,73──►139 |
|||
121 │ 67,83──►149 67,97──►163 71,79──►149 71,97──►167 73,79──►151 |
|||
126 │ 79,89──►167 83,97──►179 |
|||
───────┴────────────────────────────────────────────────────────────────────────────────────────────────────────── |
───────┴────────────────────────────────────────────────────────────────────────────────────────────────────────── |
||
Found |
Found 13 special neighbor primes: P1, P2, P1+P2-1 are primes, and P1 and P2 < 100 |
||
</pre> |
</pre> |
||
Revision as of 20:24, 6 August 2021
- Task
- Let (p1, p2) are neighbor primes. Find and show here in base ten if p1+ p2 -1 is prime, where p1, p2 < 100.
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // Special neighbor primes. Nigel Galloway: August 6th., 2021 pCache|>Seq.pairwise|>Seq.takeWhile(snd>>(>)100)|>Seq.filter(fun(n,g)->isPrime(n+g-1))|>Seq.iter(printfn "%A") </lang>
- Output:
(3, 5) (5, 7) (7, 11) (11, 13) (13, 17) (19, 23) (29, 31) (31, 37) (41, 43) (43, 47) (61, 67) (67, 71) (73, 79)
Factor
<lang factor>USING: kernel lists lists.lazy math math.primes math.primes.lists prettyprint sequences ;
lprimes dup cdr lzip [ sum 1 - prime? ] lfilter [ second 100 < ] lwhile [ . ] leach</lang>
- Output:
{ 3 5 } { 5 7 } { 7 11 } { 11 13 } { 13 17 } { 19 23 } { 29 31 } { 31 37 } { 41 43 } { 43 47 } { 61 67 } { 67 71 } { 73 79 }
Go
<lang go>package main
import (
"fmt" "rcu"
)
const MAX = 1e7 - 1
var primes = rcu.Primes(MAX)
func specialNP(limit int, showAll bool) {
if showAll { fmt.Println("Neighbor primes, p1 and p2, where p1 + p2 - 1 is prime:") } count := 0 for i := 1; i < len(primes); i++ { p2 := primes[i] if p2 >= limit { break } p1 := primes[i-1] p3 := p1 + p2 - 1 if rcu.IsPrime(p3) { if showAll { fmt.Printf("(%2d, %2d) => %3d\n", p1, p2, p3) } count++ } } ccount := rcu.Commatize(count) climit := rcu.Commatize(limit) fmt.Printf("\nFound %s special neighbor primes under %s.\n", ccount, climit)
}
func main() {
specialNP(100, true) var pow = 1000 for i := 3; i < 8; i++ { specialNP(pow, false) pow *= 10 }
}</lang>
- Output:
Neighbor primes, p1 and p2, where p1 + p2 - 1 is prime: ( 3, 5) => 7 ( 5, 7) => 11 ( 7, 11) => 17 (11, 13) => 23 (13, 17) => 29 (19, 23) => 41 (29, 31) => 59 (31, 37) => 67 (41, 43) => 83 (43, 47) => 89 (61, 67) => 127 (67, 71) => 137 (73, 79) => 151 Found 13 special neighbor primes under 100. Found 71 special neighbor primes under 1,000. Found 367 special neighbor primes under 10,000. Found 2,165 special neighbor primes under 100,000. Found 14,526 special neighbor primes under 1,000,000. Found 103,611 special neighbor primes under 10,000,000.
Julia
<lang julia>using Primes
function specialneighbors(N)
neighbors, p1 = Pair{Int}[], 2 while (p2 = nextprime(p1 + 2)) < N isprime(p2 + p1 - 1) && push!(neighbors, p1 => p2) p1 = p2 end return neighbors
end
println("Neighbor primes, p1 and p2, where p1 + p2 - 1 is prime:") println("p1 p2 p1 + p2 - 1\n--------------------------") for (p1, p2) in specialneighbors(100)
println(lpad(p1, 2), " ", rpad(p2, 7), p1 + p2 - 1)
end
</lang>
- Output:
Neighbor primes, p1 and p2, where p1 + p2 - 1 is prime: p1 p2 p1 + p2 - 1 -------------------------- 5 7 11 7 11 17 11 13 23 13 17 29 19 23 41 29 31 59 31 37 67 41 43 83 43 47 89 61 67 127 67 71 137 73 79 151
Nim
<lang Nim>import strutils, sugar
const Max = 100 - 1
func isPrime(n: Positive): bool =
if n == 1: return false if n mod 2 == 0: return n == 2 for d in countup(3, n, 2): if d * d > n: break if n mod d == 0: return false result = true
const Primes = collect(newSeq):
for n in 2..Max: if n.isPrime: n
let list = collect(newSeq):
for i in 0..<Primes.high: let p1 = Primes[i] let p2 = Primes[i + 1] if (p1 + p2 - 1).isPrime: (p1, p2)
echo "Found $1 special neighbor primes less than $2:".format(list.len, Max + 1) echo list.join(", ")</lang>
- Output:
Found 13 special neighbor primes less than 100: (3, 5), (5, 7), (7, 11), (11, 13), (13, 17), (19, 23), (29, 31), (31, 37), (41, 43), (43, 47), (61, 67), (67, 71), (73, 79)
REXX
<lang rexx>/*REXX program finds neighbor primes: P1, P2, P1+P2-1 are primes, and P1 and P2 < 100*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 100 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 5 /* " " " " " " */ call genP hi /*build semaphore array for low primes.*/
do p=1 while @.p<hi end /*p*/; lim= p-1; q= p+1 /*set LIM to prime for P; calc. 2nd HI.*/
- m= # - 1
call genP @.# + @.#m - 1 /*build semaphore array for high primes*/ w= 20 /*width of a number in any column. */ title= ' special neighbor primes: P1, P2, P1+P2-1 are primes, and P1 and P2 < ' ,
commas(hi)
if cols>0 then say ' index │'center(title, 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') found= 0; idx= 1 /*initialize # neighbor primes & index.*/ $= /*a list of neighbor primes (so far).*/
do j=1 to lim; jp= j+1; q= @.jp /*look for neighbor primes within range*/ y= @.j + q - 1; if \!.y then iterate /*is X also a prime? No, then skip it.*/ found= found + 1 /*bump the number of neighbor primes. */ if cols==0 then iterate /*Build the list (to be shown later)? */ $= $ right( @.j','q"──►"y, w) /*add neighbor prime ──► the $ list. */ 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 /*j*/
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: !.= 0; parse arg limit /*placeholders for primes (semaphores).*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " flags. */ #=5; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 to limit /*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? */ /* [↑] the above 3 lines saves time.*/ do k=5 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; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default inputs:
index │ special neighbor primes: P1, P2, P1+P2-1 are primes, and P1 and P2 < 100 ───────┼────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 3,5──►7 5,7──►11 7,11──►17 11,13──►23 13,17──►29 6 │ 19,23──►41 29,31──►59 31,37──►67 41,43──►83 43,47──►89 11 │ 61,67──►127 67,71──►137 73,79──►151 ───────┴────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 13 special neighbor primes: P1, P2, P1+P2-1 are primes, and P1 and P2 < 100
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "Special neighbor primes are:" + nl row = 0 oldPrime = 2
for n = 3 to 100
if isprime(n) and isprime(oldPrime) sum = oldPrime + n - 1 if isprime(sum) row++ see "" + oldPrime + "," + n + " => " + sum + nl ok oldPrime = n ok
next
see "Found " + row + " special neighbor primes" see "done..." + nl </lang>
- Output:
working... Special neighbor primes are: 3,5 => 7 5,7 => 11 7,11 => 17 11,13 => 23 13,17 => 29 19,23 => 41 29,31 => 59 31,37 => 67 41,43 => 83 43,47 => 89 61,67 => 127 67,71 => 137 73,79 => 151 Found 13 special neighbor primes done...
Wren
I assume that 'neighbor' primes means pairs of successive primes.
Anticipating a likely stretch goal. <lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var max = 1e7 - 1 var primes = Int.primeSieve(max)
var specialNP = Fn.new { |limit, showAll|
if (showAll) System.print("Neighbor primes, p1 and p2, where p1 + p2 - 1 is prime:") var count = 0 var p3 for (i in 1...primes.where { |p| p < limit }.count) { var p2 = primes[i] var p1 = primes[i-1] if (Int.isPrime(p3 = p1 + p2 - 1)) { if (showAll) Fmt.print("($2d, $2d) => $3d", p1, p2, p3) count = count + 1 } } Fmt.print("\nFound $,d special neighbor primes under $,d.", count, limit)
}
specialNP.call(100, true) for (i in 3..7) {
specialNP.call(10.pow(i), false)
}</lang>
- Output:
Neighbor primes, p1 and p2, where p1 + p2 - 1 is prime: ( 3, 5) => 7 ( 5, 7) => 11 ( 7, 11) => 17 (11, 13) => 23 (13, 17) => 29 (19, 23) => 41 (29, 31) => 59 (31, 37) => 67 (41, 43) => 83 (43, 47) => 89 (61, 67) => 127 (67, 71) => 137 (73, 79) => 151 Found 13 special neighbor primes under 100. Found 71 special neighbor primes under 1,000. Found 367 special neighbor primes under 10,000. Found 2,165 special neighbor primes under 100,000. Found 14,526 special neighbor primes under 1,000,000. Found 103,611 special neighbor primes under 10,000,000.
XPL0
<lang XPL0>func IsPrime(N); \Return 'true' if N is a prime number int N, I; [if N <= 1 then return false; for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true; ];
int P, P1, P2; [P:= 2; loop [P1:= P;
repeat P:= P+1; if P >= 100 then quit; until IsPrime(P); P2:= P; if IsPrime(P1+P2-1) then [IntOut(0, P1); ChOut(0, ^ ); IntOut(0, P2); ChOut(0, ^ ); IntOut(0, P1+P2-1); CrLf(0); ]; ];
]</lang>
- Output:
3 5 7 5 7 11 7 11 17 11 13 23 13 17 29 19 23 41 29 31 59 31 37 67 41 43 83 43 47 89 61 67 127 67 71 137 73 79 151