18 September, 2014

Calculating Largest known Russian Prime number

Prime Number is a number which is not perfectly divisible by more than 2 numbers. (And those two numbers which would divide a prime number are 1 and the number itself.)

A Russian Doll is a set of wooden dolls of decreasing size placed one inside the other.

A Russian Doll Prime Number is a prime number whose right digit can be repeatedly removed, and it still is prime.


e.g. 373 is a prime number. If we remove last digit,
       37 is still a prime number. If we remove last digit,
       3 is still a prime number.

Hence 373 is a Russian Doll Prime Number.

Aim of this program is to find the largest Russian Doll Prime number.

Following is an example of such a program

import java.util.HashSet;
import java.util.Set;




public class RussianDollPrimeGenerator {
    // A russian doll prime number can begin with following digits only
    private static long[] seedData={2,3,5,7};
    //only following can be subsequent digits in russian doll prime number
    private static long[] digits={1,3,7,9};
  
    public static void main(String[] args){
        // lets assume that largest known Russian Doll prime number is 0
        long largestKnownRDPrime = 0;
        // for each Seed data check
        for(long seed:seedData){
                largestKnownRDPrime=seed;
            long nextRussianDoll=getNextLargeRussianDollPrime( largestKnownRDPrime);
            // if the obtained RD is larger than yet known largest RD Prime, replace it
            if(largestKnownRDPrime<nextRussianDoll){
                largestKnownRDPrime=nextRussianDoll;
            }
        }
       
       
       
        // Results Time
        System.out.println("Largest Known Russian Prime Number-->"+largestKnownRDPrime);
       
       
    }
    // Get Russian Doll Prime number, equal or greater than the input
    private static Long  getNextLargeRussianDollPrime(long seed) {
        //assume that given number is largest known RD prime
        long largestKnownPrime=seed;
        // set to store larger RD primes obtained from this number
        Set<Long> largerPrimesSet=new HashSet<Long>();
        // verifying that seed number is prime
        if(!isprime(seed)){
            System.out.println("Invalid seed");
        }
        else{
            // append a valid possible digit at the end of seed and check if it is prime
            // if prime, add to set
            for(long digit:digits){
               
                long test=seed*10+digit;
                if(isprime(test)){
                    largerPrimesSet.add(test);
                   
                }
            }
        }
        // if there are more than one larger RD primes
        if(largerPrimesSet.size()>0){
            for(long largerPrime:largerPrimesSet){
                // Recursion to find next larger RD
                long oneStepLarger=getNextLargeRussianDollPrime(largerPrime);
                // if obtained RD prime is greater than yet known largest prime, replace the value
                if(oneStepLarger>largestKnownPrime){
                    largestKnownPrime=oneStepLarger;
                }
            }
        }
        // return largest derived RD Prime number
        return largestKnownPrime;
    }
    // method to check Prime Number
    public static boolean isprime(long n){
        boolean results=true;
        // 1 is not prime/ 2 and 3 are prime
        if(n <= 3){
           
            results= n > 1;
        }
        // if number is divisible by either 2 or 3
        else if(n % 2 == 0 || n % 3 == 0){
            results= false;
        }
        else{
            // if number is divisible by some number
            for(int i = 5; i < Math.sqrt(n) + 1;i +=6){
                if(n % i == 0 || n % (i+2) == 0){
                    results= false;
                }
            }
        }
        return results;
    }
}