SHARE
TWEET

Emirps

alefhidalgo Jun 20th, 2011 933 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top