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.

APL

<lang APL>(⎕←'Amount:',⊃⍴P)⊢P,4+P←⍪((P+4)∊P)/P←(~P∊P∘.×P)/P←1↓⍳1000</lang>

Output:

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

<lang BASIC>10 DEFINT A-Z: L=1000: DIM S(L) 20 FOR P=2 TO SQR(L) 30 IF S(P) THEN 50 40 FOR K=P*P TO L STEP P: S(K)=1: NEXT 50 NEXT 60 N=0 70 FOR P=2 TO L-4 80 IF S(P)+S(P+4)=0 THEN N=N+1: PRINT P,P+4 90 NEXT 100 PRINT "There are";N;"cousin prime pairs below";L</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
There are 41 cousin prime pairs below 1000

C

<lang c>#include <stdio.h>

include <string.h>

define LIMIT 1000

void sieve(int max, char *s) {

   int p, k;
   memset(s, 0, max);
   for (p=2; p*p<=max; p++)
       if (!s[p]) 
           for (k=p*p; k<=max; k+=p) 
               s[k]=1;

}

int main(void) {

   char primes[LIMIT+1];
   int p, count=0;
   
   sieve(LIMIT, primes);
   for (p=2; p<=LIMIT; p++) {
       if (!primes[p] && !primes[p+4]) {
           count++;
           printf("%4d: %4d\n", p, p+4);
       }
   }
   
   printf("There are %d cousin prime pairs below %d.\n", count, LIMIT);
   return 0;

}</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
There are 41 cousin prime pairs below 1000.

Cowgol

<lang cowgol>include "cowgol.coh";

const LIMIT := 1000; var sieve: uint8[LIMIT + 1]; MemZero(&sieve[0], @bytesof sieve);

var p: @indexof sieve := 2;

loop

   var n := p*p;
   if n >= LIMIT then break; end if;
   if sieve[p] == 0 then
       while n < LIMIT loop
           sieve[n] := 1;
           n := n + p;
       end loop;
   end if;
   p := p + 1;

end loop;

var count: uint8 := 0; n := 2; while n < LIMIT-4 loop

   if sieve[n] + sieve[n+4] == 0 then
       count := count + 1;
       print_i32(n as uint32);
       print_char('\t');
       print_i32(n as uint32+4);
       print_nl();
   end if;
   n := n + 1;

end loop;

print("There are "); print_i8(count); print(" cousin prime pairs below "); print_i16(LIMIT); print_nl();</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
There are 41 cousin prime pairs below 1000

Factor

Works with: Factor version 0.99 2021-02-05

<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

Translation of: Wren

<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

J

<lang J>(":,'Amount: ',":@#) (,.,.4+,.) (]#~1:p:4:+]) p:i.168</lang>

Output:

Julia

Translation of: Wren

<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.

MAD

<lang MAD> NORMAL MODE IS INTEGER

           BOOLEAN PRIME
           DIMENSION PRIME(1000)
           
           THROUGH SET, FOR P=2, 1, P.G.1000

SET PRIME(P) = 1B

           THROUGH SIEVE, FOR P=2, 1, P*P.G.1000
           WHENEVER PRIME(P)
               THROUGH MARK, FOR K=P*P, P, K.G.1000

MARK PRIME(K) = 0B

           END OF CONDITIONAL

SIEVE CONTINUE

           COUNT = 0
           THROUGH TEST, FOR P=2, 1, P.G.1000-4
           WHENEVER PRIME(P) .AND. PRIME(P+4)
               COUNT = COUNT + 1
               PRINT FORMAT COUSIN, P, P+4
           END OF CONDITIONAL

TEST CONTINUE

           PRINT FORMAT TOTAL, COUNT
           
           VECTOR VALUES COUSIN = $I4,2H: ,I4*$
           VECTOR VALUES TOTAL = $15HTOTAL COUSINS: ,I2*$
           END OF PROGRAM </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
TOTAL COUSINS: 41

Pascal

Works with: Free Pascal

Works with: Delphi

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

Library: ntheory

<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

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

Library: Wren-math

Library: Wren-fmt

<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