Twin primes
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.
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). <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 /*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 tp= tp + 2 /*This & previous prime twins? Bump tp*/ 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