Sexy primes: Difference between revisions
Content added Content deleted
(Added Algol W) |
|||
Line 28: | Line 28: | ||
::*Note that 1000033 '''SHOULD NOT''' be counted in the pair count. It is sexy, but not in a pair within the limit. However, it also '''SHOULD NOT''' be listed in the unsexy primes since it is sexy. |
::*Note that 1000033 '''SHOULD NOT''' be counted in the pair count. It is sexy, but not in a pair within the limit. However, it also '''SHOULD NOT''' be listed in the unsexy primes since it is sexy. |
||
<br><br> |
<br><br> |
||
=={{header|ALGOL W}}== |
|||
<lang algolw>begin |
|||
% find some sexy primes - primes that differ from another prime by 6 % |
|||
% implements the sieve of Eratosthenes % |
|||
procedure sieve( logical array s ( * ); integer value n ) ; |
|||
begin |
|||
% start with everything flagged as prime % |
|||
for i := 1 until n do s( i ) := true; |
|||
% sieve out the non-primes % |
|||
s( 1 ) := false; |
|||
for i := 2 until truncate( sqrt( n ) ) do begin |
|||
if s( i ) then for p := i * i step i until n do s( p ) := false |
|||
end for_i ; |
|||
end sieve ; |
|||
% adds a prime to list of sexy/unsexy primes % |
|||
procedure addPrime ( integer value p |
|||
; integer array list ( * ) |
|||
; integer value len |
|||
) ; |
|||
begin |
|||
% increment count, shuffle down the primes and add the new one % |
|||
list( 0 ) := list( 0 ) + 1; |
|||
for i := 1 until len - 1 do list( i ) := list( i + 1 ); |
|||
list( len ) := p |
|||
end addPrime ; |
|||
% counts the number of pairs of sexy primes, triplets, quadruplest and % |
|||
% quintuplets up to n % |
|||
% the counts of each kind are returned in the 0 element of the arrays % |
|||
% the last 5 ( or less if there are less than 5 ) of each type of sexy % |
|||
% prime is returned in the array elements 1 to 5 % |
|||
procedure countSexyPrimes ( logical array s ( * ) |
|||
; integer value n |
|||
; integer array pairs, triplets, quadruplets, quintuplets ( * ) |
|||
) ; |
|||
begin |
|||
integer pos2, pos3, pos4, pos5; |
|||
for i := 0 until 5 do pairs( i ) := triplets( i ) := quadruplets( i ) := quintuplets( i ) := 0; |
|||
% look for pairs etc. up to n % |
|||
% 2 cannot be a sexy prime as it is the only even prime, thus: % |
|||
% pairs can start at 7, triplets at 13, quadruplets at 19 and % |
|||
% quintuplets at 25 % |
|||
for p := 7 step 2 until 11 do begin |
|||
if s( p ) and s( p - 6 ) then addPrime( p, pairs, 5 ) |
|||
end for_p ; |
|||
for p := 13 step 2 until 17 do begin |
|||
if s( p ) and s( p - 6 ) then addPrime( p, pairs, 5 ); |
|||
if s( p ) and s( p - 6 ) and s( p - 12 ) then addPrime( p, triplets, 5 ) |
|||
end for_p ; |
|||
for p := 19 step 2 until 23 do begin |
|||
if s( p ) and s( p - 6 ) then addPrime( p, pairs, 5 ); |
|||
if s( p ) and s( p - 6 ) and s( p - 12 ) then addPrime( p, triplets, 5 ); |
|||
if s( p ) and s( p - 6 ) and s( p - 12 ) and s( p - 18 ) |
|||
then addPrime( p, quadruplets, 5 ) |
|||
end for_p ; |
|||
pos5 := 1; |
|||
pos4 := pos5 + 6; |
|||
pos3 := pos4 + 6; |
|||
pos2 := pos3 + 6; |
|||
for p := pos2 + 6 step 2 until n do begin |
|||
if s( p ) then begin |
|||
if s( pos2 ) then begin % sexy pair % |
|||
addPrime( p, pairs, 5 ); |
|||
if s( pos3 ) then begin % sexy triplet % |
|||
addPrime( p, triplets, 5 ); |
|||
if s( pos4 ) then begin % sexy quadruplet % |
|||
addPrime( p, quadruplets, 5 ); |
|||
if s( pos5 ) then begin % sexy quintuplet % |
|||
addPrime( p, quintuplets, 5 ) |
|||
end if_s_pos5 |
|||
end if_s_pos4 |
|||
end if_s_pos3 |
|||
end if_s_pos2 |
|||
end if_s_p ; |
|||
pos2 := pos2 + 2; |
|||
pos3 := pos3 + 2; |
|||
pos4 := pos4 + 2; |
|||
pos5 := pos5 + 2 |
|||
end for_p |
|||
end countSexyPrimes ; |
|||
% counts the number of unsexy primes up to n % |
|||
% the count is returned in the 0 element of the array % |
|||
% the last 5 ( or less if there are less than 5 ) unsexy prime is % |
|||
% returned in the array elements 1 to 10 % |
|||
procedure countUnsexyPrimes ( logical array s ( * ) |
|||
; integer value n |
|||
; integer array unsexy ( * ) |
|||
) ; |
|||
begin |
|||
for i := 0 until 10 do unsexy( i ) := 0; |
|||
for p := 2, 3, 5 do begin % handle primes below 7 separately % |
|||
if s( p ) and not s( p + 6 ) then addPrime( p, unsexy, 10 ) |
|||
end for_p ; |
|||
for p := 7 step 2 until n do begin |
|||
if s( p ) and not s( p - 6 ) and not s( p + 6 ) then addPrime( p, unsexy, 10 ) |
|||
end for_p |
|||
end countUnsexyPrimes ; |
|||
% shows sexy prime pairs % |
|||
procedure showPrimes ( integer value elements |
|||
; integer array primes ( * ) |
|||
; integer value arrayMax |
|||
; string(24) value title |
|||
; integer value maxPrime |
|||
) ; |
|||
begin |
|||
write( i_w := 8, s_w := 0, "Found ", primes( 0 ), " ", title, " below ", maxPrime + 1 |
|||
, i_w := 2, "; last ", ( if primes( 0 ) > arrayMax then arrayMax else primes( 0 ) ), ":" |
|||
); |
|||
write( i_w := 1, s_w := 0, " " ); |
|||
for p := 1 until arrayMax do begin |
|||
if primes( p ) not = 0 then begin |
|||
integer pn; |
|||
if elements > 1 then writeon( "(" ); |
|||
pn := primes( p ) - ( ( elements - 1 ) * 6 ); |
|||
for i := 1 until elements do begin |
|||
writeon( i_w := 1, s_w := 0, " ", pn ); |
|||
pn := pn + 6 |
|||
end for_i ; |
|||
if elements > 1 then writeon( " ) " ); |
|||
end if_primes_p_ne_0 |
|||
end for_p |
|||
end showPrimes ; |
|||
integer MAX_SEXY, MAX_PRIME; |
|||
% for the task, we need to consider primes up to 1 000 035 % |
|||
% however we must still recognise sexy primes up that limit, so we sieve % |
|||
% up to 1 000 035 + 6 % |
|||
MAX_SEXY := 1000000 + 35; |
|||
MAX_PRIME := MAX_SEXY + 6; |
|||
begin |
|||
logical array s ( 1 :: MAX_PRIME ); |
|||
integer array pairs, triplets, quadruplets, quintuplets ( 0 :: 5 ); |
|||
integer array unsexy ( 0 :: 10 ); |
|||
sieve( s, MAX_PRIME ); |
|||
countSexyPrimes( s, MAX_SEXY, pairs, triplets, quadruplets, quintuplets ); |
|||
countUnsexyPrimes( s, MAX_SEXY, unsexy ); |
|||
showPrimes( 2, pairs, 5, "sexy prime pairs", MAX_SEXY ); |
|||
showPrimes( 3, triplets, 5, "sexy prime triplets", MAX_SEXY ); |
|||
showPrimes( 4, quadruplets, 5, "sexy prime quadruplets", MAX_SEXY ); |
|||
showPrimes( 5, quintuplets, 5, "sexy prime quintuplets", MAX_SEXY ); |
|||
showPrimes( 1, unsexy, 10, "unsexy primes", MAX_SEXY ) |
|||
end |
|||
end.</lang> |
|||
{{out}} |
|||
<pre> |
|||
Found 16386 sexy prime pairs below 1000036; last 5: |
|||
( 999371 999377 ) ( 999431 999437 ) ( 999721 999727 ) ( 999763 999769 ) ( 999953 999959 ) |
|||
Found 2900 sexy prime triplets below 1000036; last 5: |
|||
( 997427 997433 997439 ) ( 997541 997547 997553 ) ( 998071 998077 998083 ) ( 998617 998623 998629 ) ( 998737 998743 998749 ) |
|||
Found 325 sexy prime quadruplets below 1000036; last 5: |
|||
( 977351 977357 977363 977369 ) ( 983771 983777 983783 983789 ) ( 986131 986137 986143 986149 ) ( 990371 990377 990383 990389 ) ( 997091 997097 997103 997109 ) |
|||
Found 1 sexy prime quintuplets below 1000036; last 1: |
|||
( 5 11 17 23 29 ) |
|||
Found 48627 unsexy primes below 1000036; last 10: |
|||
999853 999863 999883 999907 999917 999931 999961 999979 999983 1000003 |
|||
</pre> |
|||
=={{header|AWK}}== |
=={{header|AWK}}== |