Twin primes

Twin primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Twin primes are pairs of natural numbers   (P₁  and  P₂)   that satisfy the following:

1.     P₁   and   P₂   are primes
2.     P₁  +  2   =   P₂

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.

ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

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

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.

REXX

The   genP   function could be optimized for higher specifications of the limit(s).

Note that this REXX program 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

Wren

Library: Wren-math

<lang ecmascript>import "/math" for Int

var limits = [1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8] for (limit in limits) {

   var primes = Int.primeSieve(limit-1, true)
   var twins = 0
   for (i in 2...primes.count) {
       if (primes[i] == primes[i-1] + 2) twins = twins + 1
   }
   System.print("Under %(limit), there are %(twins) pairs of twin primes.")

}</lang>

Output:

Under 10, there are 2 pairs of twin primes.
Under 100, there are 8 pairs of twin primes.
Under 1000, there are 35 pairs of twin primes.
Under 10000, there are 205 pairs of twin primes.
Under 100000, there are 1224 pairs of twin primes.
Under 1000000, there are 8169 pairs of twin primes.
Under 10000000, there are 58980 pairs of twin primes.
Under 100000000, there are 440312 pairs of twin primes.