Neighbour primes
Neighbour primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Task
Find and show primes p such that p*q+2 is prime, where q is next prime after p and p < 500
See also:
11l
F isPrime(n)
L(i) 2 .. Int(n ^ 0.5)
I n % i == 0
R 0B
R 1B
print(‘p q pq+2’)
print(‘-----------------------’)
L(p) 2..498
I !isPrime(p)
L.continue
V q = p + 1
L !isPrime(q)
q++
I !isPrime(2 + p * q)
L.continue
print(p" \t "q" \t "(2 + p * q))- Output:
p q pq+2 ----------------------- 3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119
ALGOL 68
Very similar to The ALGOL 68 sample in the Special neighbor primes task
BEGIN # find adjacent primes p1, p2 such that p1*p2 + 2 s also prime #
PR read "primes.incl.a68" PR
INT max prime = 500;
[]BOOL prime = PRIMESIEVE ( ( max prime * max prime ) + 2 ); # sieve the primes to max prime ^ 2 + 2 #
[]INT low prime = EXTRACTPRIMESUPTO max prime FROMPRIMESIEVE prime; # get a list of the primes up to max prime #
# find the adjacent primes p1, p2 such that p1*p2 + 2 is prime #
FOR i TO UPB low prime - 1 DO
IF INT p1 p2 plus 2 = ( low prime[ i ] * low prime[ i + 1 ] ) + 2;
prime[ p1 p2 plus 2 ]
THEN print( ( "(", whole( low prime[ i ], -3 )
, " *", whole( low prime[ i + 1 ], -3 )
, " ) + 2 = ", whole( p1 p2 plus 2, -6 )
, newline
)
)
FI
OD
END- Output:
( 3 * 5 ) + 2 = 17 ( 5 * 7 ) + 2 = 37 ( 7 * 11 ) + 2 = 79 ( 13 * 17 ) + 2 = 223 ( 19 * 23 ) + 2 = 439 ( 67 * 71 ) + 2 = 4759 (149 *151 ) + 2 = 22501 (179 *181 ) + 2 = 32401 (229 *233 ) + 2 = 53359 (239 *241 ) + 2 = 57601 (241 *251 ) + 2 = 60493 (269 *271 ) + 2 = 72901 (277 *281 ) + 2 = 77839 (307 *311 ) + 2 = 95479 (313 *317 ) + 2 = 99223 (397 *401 ) + 2 = 159199 (401 *409 ) + 2 = 164011 (419 *421 ) + 2 = 176401 (439 *443 ) + 2 = 194479 (487 *491 ) + 2 = 239119
ALGOL W
begin % find some primes where ( p*q ) + 2 is also a prime ( where p and q are adjacent primes ) %
% sets p( 1 :: n ) to a sieve of primes up to n %
procedure sieve ( logical array p( * ) ; integer value n ) ;
begin
p( 1 ) := false; p( 2 ) := true;
for i := 3 step 2 until n do p( i ) := true;
for i := 4 step 2 until n do p( i ) := false;
for i := 3 step 2 until truncate( sqrt( n ) ) do begin
integer ii; ii := i + i;
if p( i ) then for np := i * i step ii until n do p( np ) := false
end for_i ;
end sieve ;
integer MAX_NUMBER, MAX_PRIME;
MAX_NUMBER := 500;
MAX_PRIME := MAX_NUMBER * MAX_NUMBER;
begin
logical array prime( 1 :: MAX_PRIME );
integer pCount, thisPrime, nextPrime;
% sieve the primes to MAX_PRIME %
sieve( prime, MAX_PRIME );
% find the neighbour primes %
pCount := 0;
thisPrime := 2; % 2 is the lowest prime %
while thisPrime > 0 do begin
% find the next prime after this one %
nextPrime := thisPrime + 1;
while nextPrime <= MAX_NUMBER and not prime( nextPrime ) do nextPrime := nextPrime + 1;
if nextPrime > MAX_NUMBER then thisPrime := 0
else begin
if prime( ( thisPrime * nextPrime ) + 2 ) then begin
% have another neighbour prime %
writeon( i_w := 1, s_w := 0, " ", thisPrime );
pCount := pCount + 1
end if_prime__thisPrime_x_nextPrime_plus_2 ;
thisPrime := nextPrime
end if_nextPrime_gt_MAX_NUMBER__
end while_thisPrime_gt_0 ;
write( i_w := 1, s_w := 0, "Found ", pCount, " neighbour primes up to 500" )
end
end.- Output:
3 5 7 13 19 67 149 179 229 239 241 269 277 307 313 397 401 419 439 487 Found 20 neighbour primes up to 500
AppleScript
on isPrime(n)
if (n < 6) then return ((n > 1) and (n is not 4))
if ((n mod 2 = 0) or (n mod 3 = 0) or (n mod 5 = 0)) then return false
repeat with i from 7 to (n ^ 0.5) div 1 by 30
if (n mod i = 0) or (n mod (i + 4) = 0) or (n mod (i + 6) = 0) or (n mod (i + 10) = 0) or ¬
(n mod (i + 12) = 0) or (n mod (i + 16) = 0) or (n mod (i + 22) = 0) or (n mod (i + 24) = 0) then ¬
return false
end repeat
return true
end isPrime
on neighbourPrimes(max)
set output to {}
repeat with p from 3 to max by 2
if (isPrime(p)) then
set q to p + 2
repeat until (isPrime(q))
set q to q + 2
end repeat
if (isPrime(p * q + 2)) then set end of output to p
end if
end repeat
return output
end neighbourPrimes
neighbourPrimes(499)
- Output:
{3, 5, 7, 13, 19, 67, 149, 179, 229, 239, 241, 269, 277, 307, 313, 397, 401, 419, 439, 487}
Arturo
primesUpTo500: select 1..500 => prime?
print [pad "p" 5 pad "q" 4 pad "p*q+2" 7]
print "--------------------"
i: 0
while [i < dec size primesUpTo500][
p: primesUpTo500\[i]
q: primesUpTo500\[i+1]
if prime? 2 + p * q [
prints pad to :string p 5
prints pad to :string q 5
print pad to :string 2 + p * q 8
]
i: i + 1
]
- Output:
p q p*q+2
--------------------
3 5 17
5 7 37
7 11 79
13 17 223
19 23 439
67 71 4759
149 151 22501
179 181 32401
229 233 53359
239 241 57601
241 251 60493
269 271 72901
277 281 77839
307 311 95479
313 317 99223
397 401 159199
401 409 164011
419 421 176401
439 443 194479
487 491 239119
AWK
# syntax: GAWK -f NEIGHBOUR_PRIMES.AWK
BEGIN {
print(" p q p*q+2")
print("---- ---- ------")
start = 1
stop = 499
for (p=start; p<=stop; p++) {
if (!is_prime(p)) { continue }
q = p + 1
while (!is_prime(q)) {
q++
}
if (!is_prime(p*q+2)) { continue }
printf("%4d %4d %6d\n",p,q,p*q+2)
count++
}
printf("Neighbour primes %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)
}
- Output:
p q p*q+2 ---- ---- ------ 3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119 Neighbour primes 1-499: 20
BASIC
BASIC256
function isPrime(v)
if v < 2 then return False
if v mod 2 = 0 then return v = 2
if v mod 3 = 0 then return v = 3
d = 5
while d * d <= v
if v mod d = 0 then return False else d += 2
end while
return True
end function
print "p q pq+2"
print "------------------------"
for p = 2 to 499
if not isPrime(p) then continue for
q = p + 1
while Not isPrime(q)
q += 1
end while
if not isPrime(2 + p*q) then continue for
print p; chr(9); q; chr(9); 2+p*q
next p
endPureBasic
Procedure isPrime(v.i)
If v <= 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
ElseIf v % 2 = 0 : ProcedureReturn #False
ElseIf v < 9 : ProcedureReturn #True
ElseIf v % 3 = 0 : ProcedureReturn #False
Else
Protected r = Round(Sqr(v), #PB_Round_Down)
Protected f = 5
While f <= r
If v % f = 0 Or v % (f + 2) = 0
ProcedureReturn #False
EndIf
f + 6
Wend
EndIf
ProcedureReturn #True
EndProcedure
OpenConsole()
PrintN("p q pq+2")
PrintN("----------------------")
For p.i = 2 To 499
If Not isPrime(p)
Continue
EndIf
q = p + 1
While Not isPrime(q)
q + 1
Wend
If Not isPrime(2 + p*q)
Continue
EndIf
PrintN(Str(p) + #TAB$ + Str(q) + #TAB$ + Str(2+p*q))
Next p
PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input()
CloseConsole()
Yabasic
sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
print "p q pq+2"
print "----------------------"
for p = 2 to 499
if not isPrime(p) continue
q = p + 1
while not isPrime(q)
q = q + 1
wend
if not isPrime(2 + p*q) continue
print p, chr$(9), q, chr$(9), 2+p*q
next p
end
C#
How about some other offsets besides + 2 ?
using System; using System.Collections.Generic;
using System.Linq; using static System.Console; using System.Collections;
class Program {
static void Main(string[] args) {
WriteLine ("Multiply two consecutive prime numbers, add an even number," +
" see if the result is a prime number (up to a limit).");
int c, lim = 500; var pr = PG.Primes(lim * lim).ToList();
pr = pr.TakeWhile(x => x < lim).ToList();
var Lst = new[]{ Tuple.Create(2, 2), Tuple.Create(-20, 20) };
foreach (var pair in Lst) {
bool sho = pair.Item1 == pair.Item2;
for (int ofs = pair.Item1; ofs <= pair.Item2; ofs += ofs == -2 ? 4 : 2) {
c = 0; string s = ofs.ToString("+0;-#").Insert(1, " ");
for (int i = 0, j = 1, k; j < pr.Count; i = j++)
if (PG.isPr(k = pr[i] * pr[j] + ofs))
if (sho) WriteLine (" {0,3} * {1,3} {2} = {3,-6}",
pr[i], pr[j], s, k, c++);
else c++;
WriteLine("{0,2} found under {1} for \" {2} \"", c, lim, s);
} WriteLine (); } } }
class PG { static bool[] flags; public static bool isPr(int x) {
if (x < 2) return false; return !flags[x]; }
public static IEnumerable<int> Primes(int lim) {
flags = new bool[lim + 1]; int 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; } }
- Output:
Multiply two consecutive prime numbers, add an even number, see if the result is a prime number (up to a limit).
3 * 5 + 2 = 17
5 * 7 + 2 = 37
7 * 11 + 2 = 79
13 * 17 + 2 = 223
19 * 23 + 2 = 439
67 * 71 + 2 = 4759
149 * 151 + 2 = 22501
179 * 181 + 2 = 32401
229 * 233 + 2 = 53359
239 * 241 + 2 = 57601
241 * 251 + 2 = 60493
269 * 271 + 2 = 72901
277 * 281 + 2 = 77839
307 * 311 + 2 = 95479
313 * 317 + 2 = 99223
397 * 401 + 2 = 159199
401 * 409 + 2 = 164011
419 * 421 + 2 = 176401
439 * 443 + 2 = 194479
487 * 491 + 2 = 239119
20 found under 500 for " + 2 "
5 found under 500 for " - 20 "
26 found under 500 for " - 18 "
22 found under 500 for " - 16 "
10 found under 500 for " - 14 "
22 found under 500 for " - 12 "
21 found under 500 for " - 10 "
13 found under 500 for " - 8 "
32 found under 500 for " - 6 "
20 found under 500 for " - 4 "
5 found under 500 for " - 2 "
20 found under 500 for " + 2 "
9 found under 500 for " + 4 "
36 found under 500 for " + 6 "
18 found under 500 for " + 8 "
11 found under 500 for " + 10 "
27 found under 500 for " + 12 "
20 found under 500 for " + 14 "
8 found under 500 for " + 16 "
17 found under 500 for " + 18 "
25 found under 500 for " + 20 "
Delphi
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
function GetNextPrime(var Start: integer): integer;
{Get the next prime number after Start}
{Start is passed by "reference," so the
{original variable is incremented}
begin
repeat Inc(Start)
until IsPrime(Start);
Result:=Start;
end;
procedure ShowNeighborPrimes(Memo: TMemo);
var P1,P2,P3,Cnt: integer;
var S: string;
begin
Memo.Lines.Add('Count P Q PQ+2');
Memo.Lines.Add('-----------------------');
Cnt:=0; P1:=1; P2:=1; S:='';
While P1< 500 do
begin
GetNextPrime(P2);
P3:=P1 * P2 + 2;
if IsPrime(P3) then
begin
Inc(Cnt);
S:=S+Format('%5D %4D %4D %6D',[Cnt,P1,P2,P3]);
S:=S+#$0D#$0A;
end;
P1:=P2;
end;
Memo.Lines.Add(S);
end;
- Output:
Count P Q PQ+2
-----------------------
1 3 5 17
2 5 7 37
3 7 11 79
4 13 17 223
5 19 23 439
6 67 71 4759
7 149 151 22501
8 179 181 32401
9 229 233 53359
10 239 241 57601
11 241 251 60493
12 269 271 72901
13 277 281 77839
14 307 311 95479
15 313 317 99223
16 397 401 159199
17 401 409 164011
18 419 421 176401
19 439 443 194479
20 487 491 239119
EasyLang
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
fastfunc nextprim prim .
repeat
prim += 1
until isprim prim = 1
.
return prim
.
q = 2
repeat
p = q
until p >= 500
q = nextprim q
if isprim (2 + p * q) = 1
write p & " "
.
.
- Output:
3 5 7 13 19 67 149 179 229 239 241 269 277 307 313 397 401 419 439 487
F#
This task uses Extensible Prime Generator (F#)
// Nigel Galloway. April 13th., 2021
primes32()|>Seq.pairwise|>Seq.takeWhile(fun(n,_)->n<500)|>Seq.filter(fun(n,g)->isPrime(n*g+2))|>Seq.iter(fun(n,g)->printfn "%d*%d=%d" n g (n*g+2))
- Output:
3*5=17 5*7=37 7*11=79 13*17=223 19*23=439 67*71=4759 149*151=22501 179*181=32401 229*233=53359 239*241=57601 241*251=60493 269*271=72901 277*281=77839 307*311=95479 313*317=99223 397*401=159199 401*409=164011 419*421=176401 439*443=194479 487*491=239119 Real: 00:00:00.029
Factor
USING: formatting io kernel math math.primes ;
"p q p*q+2" print
2 3
[ over 500 < ] [
2dup * 2 + dup prime?
[ 3dup "%-4d %-4d %-6d\n" printf ] when
drop nip dup next-prime
] while 2drop
- Output:
p q p*q+2 3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119
Fermat
for i = 1 to 95 do if Isprime(2+Prime(i)*Prime(i+1)) then !!Prime(i) fi odFreeBASIC
#include "isprime.bas"
dim as uinteger q
print "p q pq+2"
print "--------------------------------"
for p as uinteger = 2 to 499
if not isprime(p) then continue for
q = p + 1
while not isprime(q)
q+=1
wend
if not isprime( 2 + p*q ) then continue for
print p,q,2+p*q
next p
- Output:
p q pq+2 -------------------------------- 3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119
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
local fn FindNeighborPrimes( searchLimit as long )
NSUInteger p, q
printf @"p q p*q+2"
printf @"----------------------"
for p = 2 to searchLimit
if ( fn IsPrime(p) == NO ) then continue
q = p + 1
while ( fn IsPrime(q) == NO )
q += 1
wend
if ( fn IsPrime( p * q + 2 ) == NO ) then continue
printf @"%lu\t\t%-6lu\t%-6lu", p, q, p * q + 2
next
end fn
fn FindNeighborPrimes( 499 )
HandleEvents- Output:
p q p*q+2 ---------------------- 3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website.
In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
Go
package main
import (
"fmt"
"rcu"
)
func main() {
primes := rcu.Primes(504)
var nprimes []int
fmt.Println("Neighbour primes < 500:")
for i := 0; i < len(primes)-1; i++ {
p := primes[i]*primes[i+1] + 2
if rcu.IsPrime(p) {
nprimes = append(nprimes, primes[i])
}
}
rcu.PrintTable(nprimes, 10, 3, false)
fmt.Println("\nFound", len(nprimes), "such primes.")
}
- Output:
Neighbour primes < 500: 3 5 7 13 19 67 149 179 229 239 241 269 277 307 313 397 401 419 439 487 Found 20 such primes.
Haskell
import Data.List.Split ( divvy )
isPrime :: Int -> Bool
isPrime n
|n < 2 = False
|otherwise = null $ filter (\i -> mod n i == 0 ) [2 .. root]
where
root :: Int
root = floor $ sqrt $ fromIntegral n
solution :: [Int]
solution = map head $ filter (\li -> isPrime ((head li * last li) + 2 ))
$ divvy 2 1 $ filter isPrime [2..upTo]
where
upTo :: Int
upTo = head $ take 1 $ filter isPrime [500..]
- Output:
[3,5,7,13,19,67,149,179,229,239,241,269,277,307,313,397,401,419,439,487]
J
(#~ 1 p: {:"1) 2 (, 2 + */)\ i.&.(p:inv) 500
3 5 17
5 7 37
7 11 79
13 17 223
19 23 439
67 71 4759
149 151 22501
179 181 32401
229 233 53359
239 241 57601
241 251 60493
269 271 72901
277 281 77839
307 311 95479
313 317 99223
397 401 159199
401 409 164011
419 421 176401
439 443 194479
487 491 239119
jq
Works with gojq, the Go implementation of jq
This entry uses `is_prime` as defined at Erdős-primes#jq.
def next_prime:
if . == 2 then 3
else first(range(.+2; infinite; 2) | select(is_prime))
end;
# (not actually used)
def is_neighbour_prime:
is_prime and ((. * next_prime) + 2 | is_prime);
# The task, implemented using only `next_prime` for efficiency
{p: 2}
| while (.p < 500;
(.p|next_prime) as $np
| .emit = false
| if (.p * $np) + 2 | is_prime
then .emit = .p
else .
end
| .p = $np )
| select(.emit).emit- Output:
3 5 7 13 19 67 149 179 229 239 241 269 277 307 313 397 401 419 439 487
Julia
using Primes
isneiprime(known) = isprime(known) && isprime(known * nextprime(known + 1) + 2)
println(filter(isneiprime, primes(500)))
- Output:
[3, 5, 7, 13, 19, 67, 149, 179, 229, 239, 241, 269, 277, 307, 313, 397, 401, 419, 439, 487]
Ksh
#!/bin/ksh
# Find and show primes p such that p*q+2 is prime, where q is next prime after p and p<500
# # Variables:
#
integer MAX_PRIME=500
typeset -a parr
# # Functions:
#
# # Function _isprime(n) return 1 for prime, 0 for not prime
#
function _isprime {
typeset _n ; integer _n=$1
typeset _i ; integer _i
(( _n < 2 )) && return 0
for (( _i=2 ; _i*_i<=_n ; _i++ )); do
(( ! ( _n % _i ) )) && return 0
done
return 1
}
# # Function _neighbourprime(n) return p*q+2 if prime; 0 if not
#
function _neighbourprime {
typeset _indx ; integer _indx=$1
typeset _arr ; nameref _arr="$2"
typeset _neighbor
(( _neighbor = _arr[_indx] * _arr[_indx+1] + 2 ))
_isprime ${_neighbor}
(( $? )) && echo ${_neighbor} && return
echo 0
}
######
# main #
######
for ((i=2; i<MAX_PRIME; i++)); do
_isprime ${i} ; (( $? )) && parr+=( ${i} )
done
printf "%3s %3s %6s\n" p q p*q+2
printf "%3s %3s %6s\n" --- --- -----
for ((i=0; i<$((${#parr[*]}-1)); i++)); do
np=$(_neighbourprime ${i} parr)
(( np > 0 )) && printf "%3d %3d %6d\n" ${parr[i]} ${parr[i+1]} ${np}
done
- Output:
p q p*q+2--- --- -----
3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119
Mathematica /Wolfram Language
p = Prime@Range@PrimePi[499];
Select[p, PrimeQ[# NextPrime[#] + 2] &]
- Output:
{3, 5, 7, 13, 19, 67, 149, 179, 229, 239, 241, 269, 277, 307, 313, 397, 401, 419, 439, 487}
Nim
import strformat, sugar
const
Max1 = 499 # Maximum for first prime.
Max2 = 251_000 # Maximum for sieve (in fact 250_999 = 499 * 503 + 2).
# Sieve of Erathosthenes: false (default) is composite.
var composite: array[3..Max2, bool] # Ignore 2 as 2 * 3 + 8 is not prime.
var n = 3
while true:
let n2 = n * n
if n2 > Max2: break
if not composite[n]:
for k in countup(n2, Max2, 2 * n):
composite[k] = true
inc n, 2
template isPrime(n: int): bool = not composite[n]
let primes = collect(newSeq):
for n in countup(3, Max2, 2):
if n.isPrime: n
var p = primes[0]
var i = 0
while p <= Max1:
inc i
let q = primes[i]
if (p * q + 2).isPrime:
echo &"{p:3} {q:3} {p*q+2:6}"
p = q
- Output:
3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119
PARI/GP
Cheats a little in the sense that it requires knowing the 95th prime is 499 beforehand.
for(i=1, 95, if(isprime(2+prime(i)*prime(i+1)),print(prime(i))))Perl
use strict;
use warnings;
use ntheory <next_prime is_prime>;
my $p = 2;
do {
my $q = next_prime($p);
printf "%3d%5d%8d\n", $p, $q, $p*$q+2 if is_prime $p*$q+2;
$p = $q;
} until $p >= 500;
- Output:
3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119
Phix
function np(integer p) return is_prime(get_prime(p)*get_prime(p+1)+2) end function constant N = length(get_primes_le(500)) sequence res = apply(apply(filter(tagset(N),np),get_prime),sprint) printf(1,"Found %d such primes: %s\n",{length(res),join(shorten(res,"",5),", ")})
- Output:
Found 20 such primes: 3, 5, 7, 13, 19, ..., 397, 401, 419, 439, 487
PL/0
Formatted output isn't PL/0's forté, so this sample just shows each p1 of the p1, p2 neighbours.
This is almost identical to the PL/0 sample in the Special Neighbor primes task
var n, p1, p2, prime;
procedure isnprime;
var p;
begin
prime := 1;
if n < 2 then prime := 0;
if n > 2 then begin
prime := 0;
if odd( n ) then prime := 1;
p := 3;
while p * p <= n * prime do begin
if n - ( ( n / p ) * p ) = 0 then prime := 0;
p := p + 2;
end
end
end;
begin
p1 := 3;
p2 := 5;
while p2 < 500 do begin
n := ( p1 * p2 ) + 2;
call isnprime;
if prime = 1 then ! p1;
n := p2 + 2;
call isnprime;
while prime = 0 do begin
n := n + 2;
call isnprime;
end;
p1 := p2;
p2 := n;
end
end.
- Output:
3
5
7
13
19
67
149
179
229
239
241
269
277
307
313
397
401
419
439
487
Prolog
for swi prolog (© 2024)
primes(2, Limit):- 2 =< Limit.
primes(P, Limit):-
between(3, Limit, P),
P /\ 1 > 0, % odd
M is floor(sqrt(P)) - 1, % reverse 2*I+1
Max is M div 2,
forall(between(1, Max, I), P mod (2*I+1) > 0).
isPrime(P):-
primes(P, inf).
primeProd(PList, [P1, P2]):-
append([_, [P1, P2], _], PList),
Prod is P1 * P2 + 2,
isPrime(Prod).
showList(List):-
findnsols(10, _, (member(Pair, List), format('~|~t(~d,~d)~9+ ', Pair)), _),
nl,
fail.
showList(_).
do:-Limit is 500,
findall(P, primes(P, Limit), PrimeList),
findall(Pair, primeProd(PrimeList, Pair), P1P2List),
showList(P1P2List).
- Output:
?- do.
(3,5) (5,7) (7,11) (13,17) (19,23) (67,71) (149,151) (179,181) (229,233) (239,241)
(241,251) (269,271) (277,281) (307,311) (313,317) (397,401) (401,409) (419,421) (439,443) (487,491)
true.
Python
#!/usr/bin/python
def isPrime(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
if __name__ == '__main__':
print("p q pq+2")
print("-----------------------")
for p in range(2, 499):
if not isPrime(p):
continue
q = p + 1
while not isPrime(q):
q += 1
if not isPrime(2 + p*q):
continue
print(p, "\t", q, "\t", 2+p*q)
- Output:
p q pq+2 ----------------------- 3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119
Quackery
isprime is defined at Primality by trial division#Quackery.
[] [] 504 times
[ i^ isprime if
[ i^ join ] ]
behead swap
witheach
[ tuck over * 2 +
isprime iff
[ swap dip join ]
else drop ]
drop
echo- Output:
[ 3 5 7 13 19 67 149 179 229 239 241 269 277 307 313 397 401 419 439 487 ]
Raku
my @primes = grep &is-prime, ^Inf;
my $last_p = @primes.first: :k, * >= 500;
my $last_q = $last_p + 1;
my @cousins = @primes.head( $last_q )
.rotor( 2 => -1 )
.map(-> (\p, \q) { p, q, p*q+2 } )
.grep( *.[2].is-prime );
say .fmt('%6d') for @cousins;
- Output:
3 5 17
5 7 37
7 11 79
13 17 223
19 23 439
67 71 4759
149 151 22501
179 181 32401
229 233 53359
239 241 57601
241 251 60493
269 271 72901
277 281 77839
307 311 95479
313 317 99223
397 401 159199
401 409 164011
419 421 176401
439 443 194479
487 491 239119
REXX
Neighbor primes can also be spelled neighbour primes.
/*REXX program finds neighbor primes: P, Q, P*Q+2 are primes, and P < some specified N.*/
parse arg hi cols . /*obtain optional argument from the CL.*/
if hi=='' | hi=="," then hi= 500 /*Not specified? Then use the default.*/
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
call genP hi+50 /*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.*/
call genP @.p * @.q + 2 /*build semaphore array for high primes*/
w= 10 /*width of a number in any column. */
@neig= ' neighbor primes: p, q, p*q+2 are primes, and p < ' commas(hi)
if cols>0 then say ' index │'center(@neig, 1 + cols*(w+1) )
if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
Nprimes= 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*/
x= @.j * q + 2; if \!.x then iterate /*is X also a prime? No, then skip it.*/
Nprimes= Nprimes + 1 /*bump the number of neighbor primes. */
if cols==0 then iterate /*Build the list (to be shown later)? */
$= $ right( commas(@.j), w) /*add neighbor prime ──► the $ list. */
if Nprimes//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(Nprimes) @neig
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 ÷ by 5? (right digit).*/
if j//3==0 then iterate; if j//7==0 then iterate /*" " " 3? J ÷ by 7? */
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
- output when using the default inputs:
index │ neighbor primes: p, q, p*q+2 are primes, and p < 500 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 3 5 7 13 19 67 149 179 229 239 11 │ 241 269 277 307 313 397 401 419 439 487 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 20 neighbor primes: p, q, p*q+2 are primes, and p < 500
Ring
load "stdlib.ring"
see "working..." + nl
see "Neighbour primes are:" + nl
see "p q p*q+2" + nl
row = 0
num = 0
pr = 0
limit = 100
Primes = []
while true
pr = pr + 1
if isprime(pr)
add(Primes,pr)
num = num + 1
if num = limit
exit
ok
ok
end
for n = 1 to limit-1
prim = Primes[n]*Primes[n+1]+2
if isprime(prim)
row = row + 1
see "" + Primes[n] + " " + Primes[n+1] + " " + prim + nl
ok
next
see "Found " + row + " neighbour primes" + nl
see "done..." + nl- Output:
working... Neighbour primes are: p q p*q+2 3 5 17 5 7 37 7 11 79 13 17 223 19 23 439 67 71 4759 149 151 22501 179 181 32401 229 233 53359 239 241 57601 241 251 60493 269 271 72901 277 281 77839 307 311 95479 313 317 99223 397 401 159199 401 409 164011 419 421 176401 439 443 194479 487 491 239119 Found 20 neighbour primes done...
Rust
fn main() {
let mut primes_first : Vec<u64> = Vec::new( ) ;
primal::Primes::all( ).take_while( | n | *n < 500 ).for_each( | num |
primes_first.push( num as u64 ) ) ;
let mut current : u64 = *primes_first.iter( ).last( ).unwrap( ) + 1 ;
while ! primal::is_prime( current ) {
current += 1 ;
}
primes_first.push( current ) ;
let len = primes_first.len( ) ;
let mut primes_searched : Vec<u64> = Vec::new( ) ;
for i in 0..len - 2 {
if primal::is_prime( primes_first[ i ] * primes_first[ i + 1 ] + 2 ) {
let num = primes_first[ i ] ;
primes_searched.push( num ) ;
}
}
println!("{:?}" , primes_searched ) ;
}
- Output:
[3, 5, 7, 13, 19, 67, 149, 179, 229, 239, 241, 269, 277, 307, 313, 397, 401, 419, 439, 487]
RPL
≪ → max
≪ { } 2
WHILE DUP max < REPEAT
DUP NEXTPRIME
IF DUP2 * 2 + ISPRIME? THEN UNROT + SWAP ELSE NIP END
END DROP
≫ ≫ 'NEIGHB' STO
500 NEIGHB
- Output:
1: {3 5 7 13 19 67 149 179 229 239 241 269 277 307 313 397 401 419 439 487}
Ruby
require 'prime'
p Prime.each(500).each_cons(2).select{|p, q| (p*q+2).prime? }
- Output:
[[3, 5], [5, 7], [7, 11], [13, 17], [19, 23], [67, 71], [149, 151], [179, 181], [229, 233], [239, 241], [241, 251], [269, 271], [277, 281], [307, 311], [313, 317], [397, 401], [401, 409], [419, 421], [439, 443], [487, 491]]
Sidef
500.primes.grep {|p| p * p.next_prime + 2 -> is_prime }.say
- Output:
[3, 5, 7, 13, 19, 67, 149, 179, 229, 239, 241, 269, 277, 307, 313, 397, 401, 419, 439, 487]
Wren
import "./math" for Int
import "./fmt" for Fmt
var primes = Int.primeSieve(504)
var nprimes = []
System.print("Neighbour primes < 500:")
for (i in 0...primes.count-1) {
var p = primes[i] * primes[i+1] + 2
if (Int.isPrime(p)) nprimes.add(primes[i])
}
Fmt.tprint("$3d", nprimes, 10)
System.print("\nFound %(nprimes.count) such primes.")
- Output:
Neighbour primes < 500: 3 5 7 13 19 67 149 179 229 239 241 269 277 307 313 397 401 419 439 487 Found 20 such primes.
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 Count, P, Q;
[Count:= 0;
P:= 2; Q:= 3;
repeat if IsPrime(Q) then
[if IsPrime(P*Q+2) then
[IntOut(0, P);
ChOut(0, ^ );
Count:= Count+1;
];
P:= Q;
];
Q:= Q+2;
until P >= 500;
CrLf(0);
IntOut(0, Count);
Text(0, " neighbour primes found below 500.
");
]- Output:
3 5 7 13 19 67 149 179 229 239 241 269 277 307 313 397 401 419 439 487 20 neighbour primes found below 500.
Categories:
- Draft Programming Tasks
- Prime Numbers
- 11l
- ALGOL 68
- ALGOL 68-primes
- ALGOL W
- AppleScript
- Arturo
- AWK
- BASIC
- BASIC256
- PureBasic
- Yabasic
- C sharp
- Delphi
- SysUtils,StdCtrls
- EasyLang
- F Sharp
- Factor
- Fermat
- FreeBASIC
- FutureBasic
- Fōrmulæ
- Go
- Go-rcu
- Haskell
- J
- Jq
- Julia
- Ksh
- Mathematica
- Wolfram Language
- Nim
- PARI/GP
- Perl
- Ntheory
- Phix
- PL/0
- Prolog
- Python
- Quackery
- Raku
- REXX
- Ring
- Rust
- RPL
- Ruby
- Sidef
- Wren
- Wren-math
- Wren-fmt
- XPL0