Twin primes: Difference between revisions
m (added ;Also see: section header for OEIS references.) |
(→{{header|REXX}}: added a REXX version that counts twin prime pairs.) |
||
Line 269: | Line 269: | ||
The '''genP''' function could be optimized for higher specifications of the limit(s). |
The '''genP''' function could be optimized for higher specifications of the limit(s). |
||
=== number of twin primes === |
|||
Note that this REXX program counts the number of '''twin primes''', not the number of '''twin pairs'''. |
Note that this REXX program version counts the number of '''twin primes''', not the number of '''twin pairs'''. |
||
<lang rexx>/*REXX program counts the number of twin primes under a specified number N (or a list).*/ |
<lang rexx>/*REXX program counts the number of twin primes under a specified number N (or a list).*/ |
||
parse arg $ . /*get optional number of primes to find*/ |
parse arg $ . /*get optional number of primes to find*/ |
||
Line 304: | Line 305: | ||
409 twin primes found under 10000 |
409 twin primes found under 10000 |
||
2447 twin primes found under 100000 |
2447 twin primes found under 100000 |
||
</pre> |
|||
=== number of twin prime pairs === |
|||
Note that this REXX program version counts the number of '''twin prime pairs''', not the number of '''twin primes'''. |
|||
<lang rexx>/*REXX prgm counts the number of twin prime pairs under a specified number N (or a list)*/ |
|||
parse arg $ . /*get optional number of primes to find*/ |
|||
if $='' | $="," then $= 100 1000 10000 100000 /*Not specified? Then assume default.*/ |
|||
w= length( word($, words($) ) ) /*get length of the last number in list*/ |
|||
do i=1 for words($); x= word($, i) /*process each N─limit in the $ list.*/ |
|||
say right(genP(x),20) ' twin prime pairs found under ' right(x,max(length(x),w)) |
|||
end /*i*/ |
|||
exit 0 /*stick a fork in it, we're all done. */ |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
|||
genP: arg y; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; #= 5; tp= 2; s= @.# + 2 |
|||
do j=s by 2 while j<y+2 /*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? */ |
|||
if j // 7 ==0 then iterate /* " " " " " " seven? */ |
|||
if j //11 ==0 then iterate /* " " " " " " eleven?*/ |
|||
/* [↓] divide by the primes. ___ */ |
|||
do k=6 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 /*bump the count of number of primes. */ |
|||
@.#= j; _= # - 1 /*define J prime; point to prev. prime.*/ |
|||
if j-2\==@._ then iterate /*This & previous prime not twins? Skip*/ |
|||
if j-2<y then tp= tp + 1 /*Is this part of the twin pair? Bump.*/ |
|||
end /*j*/ |
|||
return tp</lang> |
|||
{{out|output|text= when using the default inputs:}} |
|||
<pre> |
|||
8 twin prime pairs found under 100 |
|||
35 twin prime pairs found under 1000 |
|||
205 twin prime pairs found under 10000 |
|||
1224 twin prime pairs found under 100000 |
|||
</pre> |
</pre> |
||
Revision as of 20:34, 26 July 2020
Twin primes are pairs of natural numbers (P1 and P2) that satisfy the following:
- P1 and P2 are primes
- P1 + 2 = P2
- Task
Write a program that displays the number of twin primes that can be found under a user-specified number.
- Examples
> Search Size: 100 > 8 twin prime pairs.
> Search Size: 1000 > 35 twin prime pairs.
- Also see
- The OEIS entry: A001097 Twin primes.
- The OEIS entry: A167874 The number of distinct primes < 10^n which are members of twin-prime pairs.
- The OEIS entry: A077800 List of twin primes {p, p+2}, with repetition.
- The OEIS entry: A007508 Number of twin prime pairs below 10^n.
ALGOL 68
Simplifies array bound checking by using the equivalent definition of twin primes: p and p - 2. <lang algol68>BEGIN
# count twin primes (where p and p - 2 are prime) # PR heap=128M PR # set heap memory size for Algol 68G # # sieve of Eratosthenes: sets s[i] to TRUE if i is a prime, FALSE otherwise # PROC sieve = ( REF[]BOOL s )VOID: BEGIN # start with everything flagged as prime # FOR i TO UPB s DO s[ i ] := TRUE OD; # sieve out the non-primes # s[ 1 ] := FALSE; FOR i FROM 2 TO ENTIER sqrt( UPB s ) DO IF s[ i ] THEN FOR p FROM i * i BY i TO UPB s DO s[ p ] := FALSE OD FI OD END # sieve # ; # find the maximum number to search for twin primes # INT max; print( ( "Maximum: " ) ); read( ( max, newline ) ); INT max number = max; # construct a sieve of primes up to the maximum number # [ 1 : max number ]BOOL primes; sieve( primes ); # count the twin primes # # note 2 cannot be one of the primes in a twin prime pair, so we start at 3 # INT twin count := 0; FOR p FROM 3 TO max number DO IF primes[ p ] AND primes[ p - 2 ]THEN twin count +:= 1 FI OD; print( ( "twin prime pairs below ", whole( max number, 0 ), ": ", whole( twin count, 0 ), newline ) )
END</lang>
- Output:
Maximum: 10 twin prime pairs below 10: 2
Maximum: 100 twin prime pairs below 100: 8
Maximum: 1000 twin prime pairs below 1000: 35
Maximum: 10000 twin prime pairs below 10000: 205
Maximum: 100000 twin prime pairs below 100000: 1224
Maximum: 1000000 twin prime pairs below 1000000: 8169
Maximum: 10000000 twin prime pairs below 10000000: 58980
Go
<lang go>package main
import "fmt"
func sieve(limit uint64) []bool {
limit++ // True denotes composite, false denotes prime. c := make([]bool, limit) // all false by default c[0] = true c[1] = true // no need to bother with even numbers over 2 for this task p := uint64(3) // Start from 3. for { p2 := p * p if p2 >= limit { break } for i := p2; i < limit; i += 2 * p { c[i] = true } for { p += 2 if !c[p] { break } } } return c
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n) if n < 0 { s = s[1:] } le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } if n >= 0 { return s } return "-" + s
}
func main() {
c := sieve(1e10 - 1) limit := 10 start := 3 twins := 0 for i := 1; i < 11; i++ { for i := start; i < limit; i += 2 { if !c[i] && !c[i-2] { twins++ } } fmt.Printf("Under %14s there are %10s pairs of twin primes.\n", commatize(limit), commatize(twins)) start = limit + 1 limit *= 10 }
}</lang>
- Output:
Under 10 there are 2 pairs of twin primes. Under 100 there are 8 pairs of twin primes. Under 1,000 there are 35 pairs of twin primes. Under 10,000 there are 205 pairs of twin primes. Under 100,000 there are 1,224 pairs of twin primes. Under 1,000,000 there are 8,169 pairs of twin primes. Under 10,000,000 there are 58,980 pairs of twin primes. Under 100,000,000 there are 440,312 pairs of twin primes. Under 1,000,000,000 there are 3,424,506 pairs of twin primes. Under 10,000,000,000 there are 27,412,679 pairs of twin primes.
Java
BigInteger Implementation: <lang Java> import java.math.BigInteger; import java.util.Scanner;
public class twinPrimes {
public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("Search Size: "); BigInteger max = input.nextBigInteger(); int counter = 0; for(BigInteger x = new BigInteger("3"); x.compareTo(max) <= 0; x = x.add(BigInteger.ONE)){ BigInteger sqrtNum = x.sqrt().add(BigInteger.ONE); if(x.add(BigInteger.TWO).compareTo(max) <= 0) { counter += findPrime(x.add(BigInteger.TWO), x.add(BigInteger.TWO).sqrt().add(BigInteger.ONE)) && findPrime(x, sqrtNum) ? 1 : 0; } } System.out.println(counter + " twin prime pairs."); } public static boolean findPrime(BigInteger x, BigInteger sqrtNum){ for(BigInteger divisor = BigInteger.TWO; divisor.compareTo(sqrtNum) <= 0; divisor = divisor.add(BigInteger.ONE)){ if(x.remainder(divisor).compareTo(BigInteger.ZERO) == 0){ return false; } } return true; }
} </lang>
- Output:
> Search Size: > 100 > 8 twin prime pairs.
> Search Size: > 1000 > 35 twin prime pairs.
Phix
<lang Phix>function twin_primes(integer maxp)
integer n = 0, -- result pn = 2, -- next prime index p, -- a prime, <= maxp prev_p = 2 while true do p = get_prime(pn) n += (prev_p = p-2) if p>maxp then exit end if prev_p = p pn += 1 end while return n
end function for p=1 to 9 do
integer p10 = power(10,p) printf(1,"Twin prime pairs less than %,d: %,d\n",{p10,twin_primes(p10)})
end for</lang>
- Output:
Twin prime pairs less than 10: 2 Twin prime pairs less than 100: 8 Twin prime pairs less than 1,000: 35 Twin prime pairs less than 10,000: 205 Twin prime pairs less than 100,000: 1,224 Twin prime pairs less than 1,000,000: 8,169 Twin prime pairs less than 10,000,000: 58,980 Twin prime pairs less than 100,000,000: 440,312 Twin prime pairs less than 1,000,000,000: 3,424,506
Raku
<lang perl6>use Lingua::EN::Numbers;
use Math::Primesieve;
my $p = Math::Primesieve.new;
printf "Twin prime pairs less than %14s: %s\n", comma(10**$_), comma $p.count(10**$_, :twins) for 1 .. 10;</lang>
- Output:
Twin prime pairs less than 10: 2 Twin prime pairs less than 100: 8 Twin prime pairs less than 1,000: 35 Twin prime pairs less than 10,000: 205 Twin prime pairs less than 100,000: 1,224 Twin prime pairs less than 1,000,000: 8,169 Twin prime pairs less than 10,000,000: 58,980 Twin prime pairs less than 100,000,000: 440,312 Twin prime pairs less than 1,000,000,000: 3,424,506 Twin prime pairs less than 10,000,000,000: 27,412,679
REXX
The genP function could be optimized for higher specifications of the limit(s).
number of twin primes
Note that this REXX program version counts the number of twin primes, not the number of twin pairs. <lang rexx>/*REXX program counts the number of twin primes under a specified number N (or a list).*/ parse arg $ . /*get optional number of primes to find*/ if $= | $="," then $= 100 1000 10000 100000 /*Not specified? Then assume default.*/ w= length( word($, words($) ) ) /*get length of the last number in list*/
do i=1 for words($); x= word($, i) /*process each N─limit in the $ list.*/ say right( genP(x), 20) ' twin primes found under ' right(x, max(length(x), w)) end /*i*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: arg y; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; #= 5; tp= 3; s= @.# + 2
do j=s by 2 while j<y+2 /*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? */ if j // 7 ==0 then iterate /* " " " " " " seven? */ if j //11 ==0 then iterate /* " " " " " " eleven?*/ /* [↓] divide by the primes. ___ */ do k=6 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 /*bump the count of number of primes. */ @.#= j; _= # - 1 /*define J prime; point to prev. prime.*/ if j-2\==@._ then iterate /*This & previous prime not twins? Skip*/ if j-2<y then tp= tp + 1 /*Is this part of the twin pair? Bump.*/ if j <y then tp= tp + 1 /* " " " " " " " " */ end /*j*/ return tp</lang>
- output when using the default inputs:
15 twin primes found under 100 69 twin primes found under 1000 409 twin primes found under 10000 2447 twin primes found under 100000
number of twin prime pairs
Note that this REXX program version counts the number of twin prime pairs, not the number of twin primes. <lang rexx>/*REXX prgm counts the number of twin prime pairs under a specified number N (or a list)*/ parse arg $ . /*get optional number of primes to find*/ if $= | $="," then $= 100 1000 10000 100000 /*Not specified? Then assume default.*/ w= length( word($, words($) ) ) /*get length of the last number in list*/
do i=1 for words($); x= word($, i) /*process each N─limit in the $ list.*/ say right(genP(x),20) ' twin prime pairs found under ' right(x,max(length(x),w)) end /*i*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: arg y; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; #= 5; tp= 2; s= @.# + 2
do j=s by 2 while j<y+2 /*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? */ if j // 7 ==0 then iterate /* " " " " " " seven? */ if j //11 ==0 then iterate /* " " " " " " eleven?*/ /* [↓] divide by the primes. ___ */ do k=6 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 /*bump the count of number of primes. */ @.#= j; _= # - 1 /*define J prime; point to prev. prime.*/ if j-2\==@._ then iterate /*This & previous prime not twins? Skip*/ if j-2<y then tp= tp + 1 /*Is this part of the twin pair? Bump.*/ end /*j*/ return tp</lang>
- output when using the default inputs:
8 twin prime pairs found under 100 35 twin prime pairs found under 1000 205 twin prime pairs found under 10000 1224 twin prime pairs found under 100000
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var c = Int.primeSieve(1e8-1, false) var limit = 10 var start = 3 var twins = 0 for (i in 1..8) {
var j = start while (j < limit) { if (!c[j] && !c[j-2]) twins = twins + 1 j = j + 2 } Fmt.print("Under $,11d there are $,7d pairs of twin primes.", limit, twins) start = limit + 1 limit = limit * 10
}</lang>
- Output:
Under 100 there are 8 pairs of twin primes. Under 1,000 there are 35 pairs of twin primes. Under 10,000 there are 205 pairs of twin primes. Under 100,000 there are 1,224 pairs of twin primes. Under 1,000,000 there are 8,169 pairs of twin primes. Under 10,000,000 there are 58,980 pairs of twin primes. Under 100,000,000 there are 440,312 pairs of twin primes.