alefhidalgo

Emirps

Jun 20th, 2011
1,082
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2. import java.util.SortedSet;
  3. import java.util.TreeSet;
  4.  
  5. /**
  6.  * Tuenti Programming Contest
  7.  * Challenge 3: Emirps
  8.  * @author alefhidalgo [at] gmail [dot] com
  9.  */
  10. public class Emirps {
  11.    
  12.     /* Pre-computated Emirps */
  13.     private SortedSet<Long> preComputedEmirps;
  14.     /* Last pre-computated up to */
  15.     private long lastComputedUpTo = 0;
  16.     /**
  17.      * Constructor   
  18.      */
  19.     public Emirps() {
  20.         preComputedEmirps = new TreeSet<Long>();
  21.     }
  22.     /**
  23.      * Pre-computated Emirps numbers for a best performance
  24.      * @param from
  25.      * @param to
  26.      */
  27.     private void preComp(long from, long to) {
  28.         for (long i = from; i < to; i++) {
  29.             if (isEmirp(i)) {              
  30.                 preComputedEmirps.add(i);
  31.             }
  32.         }
  33.         lastComputedUpTo = to;
  34.     }
  35.     /**
  36.      * IsPrime
  37.      * @param n
  38.      * @return
  39.      */
  40.     private boolean isPrime(Long n) {
  41.         if (n < 2)
  42.             return false;
  43.         if (n == 2 || n == 3)
  44.             return true;
  45.         if (n % 2 == 0 || n % 3 == 0)
  46.             return false;
  47.         long sqrtN = (long) Math.sqrt(n) + 1;
  48.         for (long i = 6L; i <= sqrtN; i += 6) {
  49.             if (n % (i - 1) == 0 || n % (i + 1) == 0)
  50.                 return false;
  51.         }
  52.         return true;
  53.     }
  54.     /**
  55.      * IsEmirp
  56.      * @param n
  57.      * @return
  58.      */
  59.     private boolean isEmirp(Long n) {
  60.         Long reverse = new Long(new StringBuffer(n.toString()).reverse().toString());
  61.         return isPrime(n) && isPrime(reverse) && n.compareTo(reverse)!=0;
  62.     }
  63.    
  64.     /**
  65.      * Calculate emirps sum
  66.      * @param number
  67.      * @return
  68.      */
  69.     public Long calculate(Long number) {
  70.         long result = 0;
  71.         if (number > lastComputedUpTo) {
  72.             preComp(lastComputedUpTo, number);
  73.         }
  74.         for (Long i : preComputedEmirps) {
  75.             if (i < number) {
  76.                 result += i;
  77.             }else {
  78.                 break;
  79.             }
  80.         }
  81.         return result;
  82.     }
  83.  
  84.     public static void main(String args[]) {
  85.         Emirps emirps = new Emirps();
  86.         Scanner in = new Scanner(System.in);
  87.          while (in.hasNextLine()) {
  88.              System.out.println(emirps.calculate(in.nextLong()));
  89.          }
  90.        
  91.     }
  92. }
RAW Paste Data