Cousin primes
- Definitions
In mathematics, cousin primes are prime numbers that differ by four.
For the purposes of this task a cousin prime pair is a pair of non-negative integers of the form [n, n + 4] whose elements are both primes.
- Task
Write a program to determine (and show here) all cousin prime pairs whose elements are both less than 1,000.
Optionally, show the number of such pairs.
- Also see
-
- the Wikipedia entry: cousin prime.
- the OEIS entry: A094343.
- the MathWorld entry: cousin primes.
AWK
<lang AWK>
- syntax: GAWK -f COUSIN_PRIMES.AWK
BEGIN {
start = 1 stop = 1000 for (i=start; i<=stop; i++) { if (is_prime(i) && is_prime(i+4)) { printf("%3d:%3d%1s",i,i+4,++count%10?"":"\n") } } printf("\nCousin 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)
} </lang>
- Output:
3: 7 7: 11 13: 17 19: 23 37: 41 43: 47 67: 71 79: 83 97:101 103:107 109:113 127:131 163:167 193:197 223:227 229:233 277:281 307:311 313:317 349:353 379:383 397:401 439:443 457:461 463:467 487:491 499:503 613:617 643:647 673:677 739:743 757:761 769:773 823:827 853:857 859:863 877:881 883:887 907:911 937:941 967:971 Cousin primes 1-1000: 41
Factor
<lang factor>USING: kernel lists lists.lazy math math.primes prettyprint sequences ;
- lcousins ( -- list )
L{ { 3 7 } } 7 11 [ [ 6 + ] lfrom-by ] bi@ lzip lappend-lazy [ [ prime? ] all? ] lfilter ;
lcousins [ last 1000 < ] lwhile [ . ] leach</lang>
- Output:
{ 3 7 } { 7 11 } { 13 17 } { 19 23 } { 37 41 } { 43 47 } { 67 71 } { 79 83 } { 97 101 } { 103 107 } { 109 113 } { 127 131 } { 163 167 } { 193 197 } { 223 227 } { 229 233 } { 277 281 } { 307 311 } { 313 317 } { 349 353 } { 379 383 } { 397 401 } { 439 443 } { 457 461 } { 463 467 } { 487 491 } { 499 503 } { 613 617 } { 643 647 } { 673 677 } { 739 743 } { 757 761 } { 769 773 } { 823 827 } { 853 857 } { 859 863 } { 877 881 } { 883 887 } { 907 911 } { 937 941 } { 967 971 }
Go
<lang go>package main
import "fmt"
func isPrime(n int) bool {
switch { case n < 2: return false case n%2 == 0: return n == 2 case n%3 == 0: return n == 3 default: d := 5 for d*d <= n { if n%d == 0 { return false } d += 2 if n%d == 0 { return false } d += 4 } return true }
}
func main() {
count := 0 fmt.Println("Cousin prime pairs whose elements are less than 1,000:") for i := 3; i <= 995; i += 2 { if isPrime(i) && isPrime(i+4) { fmt.Printf("%3d:%3d ", i, i+4) count++ if count%7 == 0 { fmt.Println() } if i != 3 { i += 4 } else { i += 2 } } } fmt.Printf("\n\n%d pairs found\n", count)
}</lang>
- Output:
Cousin prime pairs whose elements are less than 1,000: 3: 7 7: 11 13: 17 19: 23 37: 41 43: 47 67: 71 79: 83 97:101 103:107 109:113 127:131 163:167 193:197 223:227 229:233 277:281 307:311 313:317 349:353 379:383 397:401 439:443 457:461 463:467 487:491 499:503 613:617 643:647 673:677 739:743 757:761 769:773 823:827 853:857 859:863 877:881 883:887 907:911 937:941 967:971 41 pairs found
Julia
<lang julia>using Primes
let
p = primesmask(1000) println("Cousin prime pairs under 1,000:") pcount = 0 for i in 2:996 if p[i] && p[i + 4] pcount += 1 print(lpad(i, 4), ":", rpad(i + 4, 4), pcount % 8 == 0 ? "\n" : "") end end println("\n\n$pcount pairs found.")
end
</lang>
- Output:
Cousin prime pairs under 1,000: 3:7 7:11 13:17 19:23 37:41 43:47 67:71 79:83 97:101 103:107 109:113 127:131 163:167 193:197 223:227 229:233 277:281 307:311 313:317 349:353 379:383 397:401 439:443 457:461 463:467 487:491 499:503 613:617 643:647 673:677 739:743 757:761 769:773 823:827 853:857 859:863 877:881 883:887 907:911 937:941 967:971 41 pairs found.
Pascal
Sieving only odd numbers.
<lang pascal>program Cousin_primes; //Free Pascal Compiler version 3.2.1 [2020/11/03] for x86_64fpc {$IFDEF FPC}
{$MODE DELPHI} {$Optimization ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} const
MAXNUMBER = 100*1000*1000;// > 3 MAXLIMIT = (MAXNUMBER-1) DIV 2;
type
tChkprimes = array of byte;//prime == 1 , nonprime == 0 tPrimes = array of Uint32;
var
primes :tPrimes; //here starting with 3
procedure OutCount(lmt,cnt:NativeInt); Begin
writeln(cnt,' cousin primes up to ',lmt);
end;
procedure InitPrimes; var
Chkprimes:tChkprimes;
//NativeUInt i DIV 2 is only SHR 1,otherwise extension to Int64
i,j,CountOfPrimes : NativeUInt;
begin
SetLength(Chkprimes,MAXLIMIT+1); fillchar(Chkprimes[0],length(Chkprimes),#1); //estimate count of primes CountOfPrimes := trunc(MAXNUMBER/(ln(MAXNUMBER)-1.08))+100; SetLength(primes,CountOfPrimes+1); //sieve of eratosthenes only odd numbers // i = 2*j+1 Chkprimes[0] := 0;// 0 -> 2*0+1 = 1 i := 1; repeat if Chkprimes[(i-1) DIV 2] <> 0 then Begin // convert i*i into j j := (i*i-1) DIV 2; if j> MAXLIMIT then break; repeat Chkprimes[j]:= 0; inc(j,i); until j> MAXLIMIT; end; inc(i,2); until false; j := 0; For i := 1 to MAXLIMIT do IF Chkprimes[i]<>0 then Begin primes[j] := 2*i+1; inc(j); if j>CountOfPrimes then Begin CountOfPrimes += 400; setlength(Primes,CountOfPrimes); end; end; setlength(primes,j); setlength(Chkprimes,0);
end;
var
i,lmt,cnt,primeCount : NativeInt;
BEGIN
InitPrimes; //only exception, that the index difference is greater 1 write(primes[0]:3,':',primes[2]:3,' '); cnt := 1; lmt := 1000; For i := 1 to High(primes) do Begin if primes[i] >lmt then break; IF primes[i]-primes[i-1] = 4 then Begin write(primes[i-1]:3,':',primes[i]:3,' '); inc(cnt); If cnt MOD 6 = 0 then writeln; end; end; writeln; OutCount(lmt,cnt); writeln; cnt := 1; lmt *= 10; primeCount := High(primes); For i := 1 to primeCount do Begin if primes[i] >lmt then Begin OutCount(lmt,cnt); lmt *= 10; end; inc(cnt,ORD(primes[i]-primes[i-1] = 4)); end; OutCount(MAXNUMBER,cnt); setlength(primes,0);
END.</lang>
- Output:
3: 7 7: 11 13: 17 19: 23 37: 41 43: 47 67: 71 79: 83 97:101 103:107 109:113 127:131 163:167 193:197 223:227 229:233 277:281 307:311 313:317 349:353 379:383 397:401 439:443 457:461 463:467 487:491 499:503 613:617 643:647 673:677 739:743 757:761 769:773 823:827 853:857 859:863 877:881 883:887 907:911 937:941 967:971 41 cousin primes up to 1000 203 cousin primes up to 10000 1216 cousin primes up to 100000 8144 cousin primes up to 1000000 58622 cousin primes up to 10000000 440258 cousin primes up to 100000000 real 0m0,484s
Perl
<lang perl>use warnings; use feature 'say'; use ntheory 'is_prime';
my($limit, @cp) = 1000; is_prime($_) and is_prime($_+4) and push @cp, "$_/@{[$_+4]}" for 2..$limit; say @cp . " cousin prime pairs < $limit:\n" . (sprintf "@{['%8s' x @cp]}", @cp) =~ s/(.{56})/$1\n/gr;</lang>
- Output:
41 cousin prime pairs < 1000: 3/7 7/11 13/17 19/23 37/41 43/47 67/71 79/83 97/101 103/107 109/113 127/131 163/167 193/197 223/227 229/233 277/281 307/311 313/317 349/353 379/383 397/401 439/443 457/461 463/467 487/491 499/503 613/617 643/647 673/677 739/743 757/761 769/773 823/827 853/857 859/863 877/881 883/887 907/911 937/941 967/971
Phix
<lang Phix>function has_cousin(integer p) return is_prime(p+4) end function for n=2 to 7 do
integer tn = power(10,n) sequence res = filter(get_primes_le(tn-9),has_cousin) res = columnize({res,sq_add(res,4)}) printf(1,"%,d cousin prime pairs less than %,d found: %v\n",{length(res),tn,shorten(res,"",min(4,5-floor(n/2)))})
end for</lang> (Uses tn-9 instead of the more obvious tn-4 since none of 96,95,94,93,92 or similar could ever be prime. Note that {97,101} is deliberately excluded from < 100.)
- Output:
8 cousin prime pairs less than 100 found: {{3,7},{7,11},{13,17},{19,23},{37,41},{43,47},{67,71},{79,83}} 41 cousin prime pairs less than 1,000 found: {{3,7},{7,11},{13,17},{19,23},"...",{883,887},{907,911},{937,941},{967,971}} 203 cousin prime pairs less than 10,000 found: {{3,7},{7,11},{13,17},"...",{9787,9791},{9829,9833},{9883,9887}} 1,216 cousin prime pairs less than 100,000 found: {{3,7},{7,11},{13,17},"...",{99709,99713},{99829,99833},{99877,99881}} 8,144 cousin prime pairs less than 1,000,000 found: {{3,7},{7,11},"...",{999769,999773},{999979,999983}} 58,622 cousin prime pairs less than 10,000,000 found: {{3,7},{7,11},"...",{9999217,9999221},{9999397,9999401}}
REXX
This REXX version allows the limit to be specified, as well as the number of cousin prime pairs to be shown per line. <lang rexx>/*REXX program counts/shows the number of cousin prime pairs under a specified number N.*/ parse arg hi cols . /*get optional number of primes to find*/ if hi== | hi=="," then hi= 1000 /*Not specified? Then assume default.*/ if cols== | cols=="," then cols= 10 /* " " " " " .*/ Ocols= cols; cols= abs(cols) /*Use the absolute value of cols. */ call genP hi-1 /*generate all primes under N. */ pairs= 0; dups= 0 /*initialize # cousin prime pairs; dups*/ $= /*a list of cousin prime pairs (so far)*/
do j=1 while @.j\==.; c= @.j - 4 /*lets hunt for cousin prime pairs. */ if \!.c then iterate /*Not a lowe cousin pair? Then skip it.*/ pairs= pairs + 1 /*bump the count of cousin prime pairs.*/ if @.j==11 then dups= dups + 1 /*take care to note if there is a dup. */ if Ocols<1 then iterate /*Build the list (to be shown later)? */ $= $ ' ('@.j-4","@.j')' /*add the cousin pair to the $ list. */ if pairs//cols\==0 then iterate /*have we populated a line of output? */ say strip($); $= /*display what we have so far (cols). */ end /*j*/
if $\== then say strip($) /*possible display some residual output*/ say say 'found ' pairs " cousin prime pairs." say 'found ' pairs*2-dups " unique cousin primes." exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: parse arg n; @.=.; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; @.7=17; #= 7
!.=0; !.2=1; !.3=1; !.5=1; !.7=1; !.11=1; !.13=1; !.17=1 do j=@.7+2 by 2 while j<=hi /*continue on with the next odd prime. */ parse var j -1 _ /*obtain the last digit of the J var.*/ if _ ==5 then iterate /*is this integer a multiple of five? */ if j // 3 ==0 then iterate /* " " " " " " three? */ /* [↓] divide by the primes. ___ */ do k=4 to # while k*k<=j /*divide J by other primes ≤ √ J */ if j//@.k == 0 then iterate j /*÷ by prev. prime? ¬prime ___ */ end /*k*/ /* [↑] only divide up to √ J */ #= # + 1; @.#= j; !.j= 1 /*bump prime count; assign prime & flag*/ end /*j*/ return</lang>
- output when using the default inputs:
(3,7) (7,11) (13,17) (19,23) (37,41) (43,47) (67,71) (79,83) (97,101) (103,107) (109,113) (127,131) (163,167) (193,197) (223,227) (229,233) (277,281) (307,311) (313,317) (349,353) (379,383) (397,401) (439,443) (457,461) (463,467) (487,491) (499,503) (613,617) (643,647) (673,677) (739,743) (757,761) (769,773) (823,827) (853,857) (859,863) (877,881) (883,887) (907,911) (937,941) (967,971) found 41 cousin prime pairs. found 81 unique cousin primes.
Raku
Filter
Favoring brevity over efficiency due to the small range of n, the most concise solution is: <lang perl6>say grep *.all.is-prime, map { $_, $_+4 }, 2..999;</lang>
- Output:
((3 7) (7 11) (13 17) (19 23) (37 41) (43 47) (67 71) (79 83) (97 101) (103 107) (109 113) (127 131) (163 167) (193 197) (223 227) (229 233) (277 281) (307 311) (313 317) (349 353) (379 383) (397 401) (439 443) (457 461) (463 467) (487 491) (499 503) (613 617) (643 647) (673 677) (739 743) (757 761) (769 773) (823 827) (853 857) (859 863) (877 881) (883 887) (907 911) (937 941) (967 971))
Infinite List
A more efficient and versatile approach is to generate an infinite list of cousin primes, using this info from https://oeis.org/A023200 :
- Apart from the first term, all terms are of the form 6n + 1.
<lang perl6>constant @cousins = (3, 7, *+6 … *).map: -> \n { (n, n+4) if (n & n+4).is-prime };
my $count = @cousins.first: :k, *.[0] > 1000;
.say for @cousins.head($count).batch(9);</lang>
- Output:
((3 7) (7 11) (13 17) (19 23) (37 41) (43 47) (67 71) (79 83) (97 101)) ((103 107) (109 113) (127 131) (163 167) (193 197) (223 227) (229 233) (277 281) (307 311)) ((313 317) (349 353) (379 383) (397 401) (439 443) (457 461) (463 467) (487 491) (499 503)) ((613 617) (643 647) (673 677) (739 743) (757 761) (769 773) (823 827) (853 857) (859 863)) ((877 881) (883 887) (907 911) (937 941) (967 971))
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "cousin primes are:" + nl
ind = 0 row = 0 limit = 1000 cousin = []
for n = 1 to limit
if isprime(n) and isprime(n+4) row = row + 1 ind1 = find(cousin,n) ind2 = find(cousin,n+4) if ind1 < 1 add(cousin,n) ok if ind2 < 1 add(cousin,n+4) ok see "(" + n + ", " + (n+4) + ") " if row%5 = 0 see nl ok ok
next
lencousin = len(cousin) see nl + "found " + row + " cousin prime pairs." + nl see "found " + lencousin + " unique cousin primes." + nl
see "done..." + nl </lang>
- Output:
working... cousin primes are: (3, 7) (7, 11) (13, 17) (19, 23) (37, 41) (43, 47) (67, 71) (79, 83) (97, 101) (103, 107) (109, 113) (127, 131) (163, 167) (193, 197) (223, 227) (229, 233) (277, 281) (307, 311) (313, 317) (349, 353) (379, 383) (397, 401) (439, 443) (457, 461) (463, 467) (487, 491) (499, 503) (613, 617) (643, 647) (673, 677) (739, 743) (757, 761) (769, 773) (823, 827) (853, 857) (859, 863) (877, 881) (883, 887) (907, 911) (937, 941) (967, 971) found 41 cousin prime pairs. found 81 unique cousin primes. done...
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var c = Int.primeSieve(999, false) var count = 0 System.print("Cousin prime pairs whose elements are less than 1,000:") var i = 3 while (i <= 995) {
if (!c[i] && !c[i + 4]) { Fmt.write("$3d:$3d ", i, i + 4) count = count + 1 if ((count % 7) == 0) System.print() i = (i != 3) ? i + 4 : i + 2 } i = i + 2
} System.print("\n\n%(count) pairs found")</lang>
- Output:
Cousin prime pairs whose elements are less than 1,000: 3: 7 7: 11 13: 17 19: 23 37: 41 43: 47 67: 71 79: 83 97:101 103:107 109:113 127:131 163:167 193:197 223:227 229:233 277:281 307:311 313:317 349:353 379:383 397:401 439:443 457:461 463:467 487:491 499:503 613:617 643:647 673:677 739:743 757:761 769:773 823:827 853:857 859:863 877:881 883:887 907:911 937:941 967:971 41 pairs found