Neighbour primes
- Task
Find and show primes p such that p*q+2 is prime, where q is next prime after p and p < 500
ALGOL W
<lang algolw>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.</lang>
- 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
Factor
<lang 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</lang>
- 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
<lang fermat>for i = 1 to 95 do if Isprime(2+Prime(i)*Prime(i+1)) then !!Prime(i) fi od</lang>
FreeBASIC
<lang freebasic>#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</lang>
- 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
Go
<lang 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.")
}</lang>
- 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.
Julia
<lang julia>using Primes
isneiprime(known) = isprime(known) && isprime(known * nextprime(known + 1) + 2) println(filter(isneiprime, primes(500)))
</lang>
- Output:
[3, 5, 7, 13, 19, 67, 149, 179, 229, 239, 241, 269, 277, 307, 313, 397, 401, 419, 439, 487]
PARI/GP
Cheats a little in the sense that it requires knowing the 95th prime is 499 beforehand. <lang parigp>for(i=1, 95, if(isprime(2+prime(i)*prime(i+1)),print(prime(i))))</lang>
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
Raku
<lang perl6>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;</lang>
- 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
Ring
<lang 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 </lang>
- 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...
Wren
<lang ecmascript>import "/math" for Int import "/seq" for Lst 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])
} for (chunk in Lst.chunks(nprimes, 10)) Fmt.print("$3d", chunk) System.print("\nFound %(nprimes.count) such primes.")</lang>
- 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.