Tag Archives: prime

Twin prime

A twin prime is a prime number that has a prime gap of two, in other words, differs from another prime number by two, for example the twin prime pair (41, 43). Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin or prime pair.

I have already discussed a method to determine whether a given integer is prime or not (primality test) in my earlier post “Prime time“. I would be using the function discussed in the earlier post for primality test. The logic of the program is essentially to test whether or not the number and the number obtained by adding two to it, are both prime numbers or not. The efficiency of the twin prime program is dependent on the efficiency of the primality test function i.e. isPrime() function.

The efficiency can be increased, if we take care to ensure that short circuit evaluation takes place. Short-circuit evaluation, minimal evaluation, or McCarthy evaluation denotes the semantics of some Boolean operators in some programming languages in which the second argument is executed or evaluated only if the first argument does not suffice to determine the value of the expression: when the first argument of the AND function evaluates to false, the overall value must be false; and when the first argument of the OR function evaluates to true, the overall value must be true. In other words do not sore the result of the isPrime() function in seperate boolean variables and then compare it using if statements because then the function isPrime() would be invoked twice. Please note that there is no point in checking primality for (number+2) if the number is not prime.

The Java program to display twin prime or prime pairs between any given range is as follows:

class TwinPrime{
    public static boolean isPrime(int number){
        int factorCount=0;
        if(number<2) return false;
        else if(number==2) return true;
        else if(number%2==0) return false;
        else{
            int limit = (int)Math.sqrt(number);
            for(int i=3; i<=limit;i+=2){
                if(number%i==0){
                    return false;
                }
            }
        }
        return true;
    }
    public static void displayTwinPrime( int from, int to ){
        for( int i=from; i<=to-2; i++ ){
            if( isPrime( i ) && isPrime( i + 2 ) ){
                System.out.println( "(" + i + ", " + (i+2) + ") " );
            }
        }
    }
    public static void main(String args[]){
        displayTwinPrime( 1, 44 );
    }
}

The output of the above program is as follows:

(3, 5) 
(5, 7) 
(11, 13) 
(17, 19) 
(29, 31) 
(41, 43)

As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.