• API
• FAQ
• Tools
• Archive
daily pastebin goal
16%
SHARE
TWEET

# Prime Factorization First 26 Primes

a guest Mar 18th, 2019 51 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) {
61.                     str.append((char)(i + 97));
62.
63.                     num /= divisor;
64.                     num_half = num/2;
65.
66.                     break;
67.                 }
68.             }
69.         }
70.