Cousin primes: Difference between revisions
Line 25: | Line 25: | ||
let |
let |
||
p = primesmask(1000) |
p = primesmask(1000) |
||
found = Dict{Int, String}() |
|||
println("Cousin prime pairs under 1,000:") |
println("Cousin prime pairs under 1,000:") |
||
pcount = 0 |
pcount = 0 |
Revision as of 02:59, 19 March 2021
- 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.
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}
const
ERROR_SPACE = -243; MAXZAHL = 1000;// > 3 MAXLIMIT = (MAXZAHL-1) DIV 2; //estimate CountOfPrimes = trunc(MAXZAHL/(ln(MAXZAHL)-1.08))+100;
type
tChkprimes = array[0..MAXLIMIT] of byte;//prime == 1 , nonprime == 0 tPrimes: array[0..CountOfPrimes]of Uint32;
{$ELSE}
{$APPTYPE CONSOLE}
const
ERROR_SPACE = 243; MAXZAHL = 1000;// > 3 MAXLIMIT = (MAXZAHL-1) DIV 2;
type
tChkprimes = array of byte; tPrimes = array of Uint32;
var
CountOfPrimes: Uint32;
{$ENDIF}
var
Chkprimes:tChkprimes; primes :tPrimes; //here starting with 3 primeCount:NativeInt;
procedure InitPrimes;
//sieve of eratothenes
var
i,j : NativeInt;
begin
// i = 2*j+1
{$IFDEF FPC}
fillchar(Chkprimes,SizeOf(tChkprimes),#1);
{$ELSE}
fillchar(Chkprimes[0],length(Chkprimes),#1);
{$ENDIF}
Chkprimes[0] := 0; i := 1; repeat if Chkprimes[(i-1) DIV 2] <> 0 then Begin 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); end;
// writeln('prime count ',j+1,' til ',MAXZAHL); //count "2"
primeCount := j-1;
IF CountOfPrimes-primeCount < 0 then begin writeln(' Need more space for primes ', primeCount-CountOfPrimes); HALT(ERROR_SPACE); end;
end; var
i,cnt : NativeInt;
BEGIN {$IFNDEF FPC}
CountOfPrimes := trunc(MAXZAHL/(ln(MAXZAHL)-1.08))+100; SetLength(primes,CountOfPrimes+1); SetLength(Chkprimes,CountOfPrimes+1);
{$ENDIF}
InitPrimes; //only exception, that the index difference is greater 1 write(primes[0]:3,':',primes[2]:3,' '); cnt := 1; For i := 1 to primeCount do 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; writeln; writeln(cnt,' cousin primes found');
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 27 cousin primes found
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 the number of twin prime pairs under a specified number N. */ parse arg n cols . /*get optional number of primes to find*/ if n== | n=="," then n= 1000 /*Not specified? Then assume default.*/ if cols== | cols=="," then cols= 10 /*Not specified? Then assume default.*/ call genP n-1 /*generate all primes under N. */ pairs= 0; dups= 0 /*initialize # cousin prime pairs; dups*/ dups= 0 /*the number of duplicate cousin primes*/ $= /*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.*/ $= $ ' ('@.j-4","@.j')'; pairs= pairs + 1 /*add cousin pair to the list. */ if @.j==11 then dups= dups + 1 /*take care to note if there is a dup. */ 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<=n /*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.
Ring
<lang ring> load "stdlib.ring"
see "working..." + nl see "cousin primes are:" + nl
ind = 0 row = 0 limit = 1000
for n = 1 to limit
if isprime(n) and isprime(n+4) row = row + 1 see "(" + n + ", " + (n+4) + ") " if row%5 = 0 see nl ok ok
next
see nl + "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) done...
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))
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