Advertisement
Guest User

Find Deletable Primes (LTT Problem solving 1)

a guest
Jul 28th, 2014
268
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.89 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4.  
  5. public class DeletablePrimes {
  6.     public static void main(String[] args){
  7.         List<Integer> primes = primes(10000000);
  8.         List<Integer> deletablePrimes = new ArrayList<Integer>();
  9.         long sum = 0;
  10.         for(int i : primes){
  11.             if(isDeletablePrime(Integer.toString(i))){
  12.                 deletablePrimes.add(i);
  13.                 sum+=i;
  14.             }
  15.         }
  16.         System.out.println(deletablePrimes.size());
  17.         System.out.println(sum);
  18.     }
  19.     public static List<Integer> primes(int n){
  20.         int p = 2;
  21.         boolean[] primes_b = new boolean[n];
  22.         Arrays.fill(primes_b, true);
  23.         primes_b[0] = false;
  24.         primes_b[1] = false;
  25.         outerloop: while(p<n){
  26.             for(int x=2; p*x<n;x++){
  27.                 primes_b[x*p] = false;
  28.             }  
  29.             for(int i = 2; i<=primes_b.length;i++){
  30.                 //selecting next p
  31.                 try{
  32.                     if(primes_b[i]){if(i>p){p=i;break;}}
  33.                 }catch(IndexOutOfBoundsException e){
  34.                     break outerloop;
  35.                 }
  36.             }
  37.         }
  38.         List<Integer> primes = new ArrayList<Integer>();
  39.         for(int i =0;i<primes_b.length;i++){
  40.             if(primes_b[i]){primes.add(i);};
  41.         }
  42.         return primes;
  43.     }
  44.     public static boolean isprime(int num){
  45.         if(num < 2) return false;
  46.         if(num == 2 || num == 3) return true;
  47.         if(num%2 == 0 || num%3 == 0) return false;
  48.         long sqrtN = (long)Math.sqrt(num)+1;
  49.         for(long i = 6L; i <= sqrtN; i += 6) {
  50.             if(num%(i-1) == 0 || num%(i+1) == 0) return false;
  51.         }
  52.         return true;
  53.     }
  54.     public static boolean isDeletablePrime(String prime){
  55.         if(Integer.parseInt(prime.substring(0,1))==0){return false;};
  56.         if(prime.length()==1){
  57.             if(isprime(Integer.parseInt(prime))){
  58.                 return true;
  59.             }else{
  60.                 return false;
  61.             }
  62.         }
  63.         for(int r = 0; r<prime.length();r++){
  64.             String buffer = prime.substring(0,r)+prime.substring(r+1,prime.length());
  65.             if(isprime(Integer.parseInt(buffer))){
  66.                 if(isDeletablePrime(buffer)){
  67.                     return true;
  68.                 }
  69.             }
  70.         }
  71.         return false;
  72.     }
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement