SHARE
TWEET

Prime Factorization First 26 Primes

a guest Mar 18th, 2019 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class Main
  4. {
  5.     static int[] primes = new int[] {
  6.         02, 03, 05, 07, 11, 13, 17, 19, 23, 29,
  7.         31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
  8.         73, 79, 83, 89, 97, 101 };
  9.    
  10.     static boolean contains(long x, int l, int r) {
  11.         if (r >= l) {
  12.             int mid = l + (r - l) / 2;
  13.            
  14.             if (primes[mid] == x)
  15.                 return true;
  16.                
  17.             if (primes[mid] > x)
  18.                 return contains(x, l, mid - 1);
  19.            
  20.             return contains(x, mid + 1, r);
  21.         }
  22.        
  23.         return false;
  24.     }
  25.    
  26.     static int find(long x, int l, int r) {
  27.         if (r >= l) {
  28.             int mid = l + (r - l) / 2;
  29.            
  30.             if (primes[mid] == x)
  31.                 return mid;
  32.                
  33.             if (primes[mid] > x)
  34.                 return find(x, l, mid - 1);
  35.            
  36.             return find(x, mid + 1, r);
  37.         }
  38.        
  39.         return -1;
  40.     }
  41.    
  42.     public static void main(String[] args) {
  43.         Scanner scan = new Scanner(System.in);
  44.         ArrayList<Long> factorization = new ArrayList<Long>();
  45.         StringBuilder str = new StringBuilder();
  46.        
  47.         long num = scan.nextLong();
  48.        
  49.         while (!contains(num, 0, 25)) {
  50.             long num_half = num/2;
  51.            
  52.             for (int i = 0; i < 26; i++) {
  53.                 int divisor = primes[i];
  54.                
  55.                 if (divisor > num_half) break;
  56.                
  57.                 boolean divisible = (long)(num/divisor) * divisor == num;
  58.                
  59.                 if (divisible) {
  60.                     factorization.add((long)divisor);
  61.                     str.append((char)(i + 97));
  62.                    
  63.                     num /= divisor;
  64.                     num_half = num/2;
  65.                    
  66.                     break;
  67.                 }
  68.             }
  69.         }
  70.        
  71.         factorization.add(num);
  72.         str.append((char)(find(num, 0, 25) + 97));
  73.        
  74.         for (int i = 0; i < factorization.size(); i++) {
  75.             System.out.println(factorization.get(i));
  76.         }
  77.        
  78.         System.out.println(str);
  79.     }
  80. }
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