Advertisement
Glenpl

java number factorization

Jun 17th, 2015
269
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.25 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. public class MainClass {
  5.  
  6.     static ArrayList<Integer> primes = new ArrayList<Integer>();
  7.  
  8.     public static void main(String[] args) {
  9.         generatePrimes(50000);
  10.  
  11.         @SuppressWarnings("resource")
  12.         Scanner input = new Scanner(System.in);
  13.  
  14.         int num = input.nextInt();
  15.  
  16.         ArrayList<Integer> factors = factorize(num);
  17.  
  18.         System.out.print(factors.toString());
  19.     }
  20.  
  21.     public static ArrayList<Integer> factorize(int num) {
  22.  
  23.         ArrayList<Integer> factors = new ArrayList<Integer>();
  24.  
  25.         if (isPrime(num))
  26.             factors.add(num);
  27.         else {
  28.             while (num != 1) {
  29.                 for (int prime : primes) {
  30.                     while ((num % prime) == 0) {
  31.                         factors.add(prime);
  32.                         num /= prime;
  33.                         if (num == 1)
  34.                             return factors;
  35.                     }
  36.                 }
  37.                 generatePrimes(200000);
  38.             }
  39.         }
  40.  
  41.         return factors;
  42.     }
  43.  
  44.     private static void generatePrimes(int limit) {
  45.         primes.clear();
  46.         for (int i = 2; primes.size() < limit; i++)
  47.             if (isPrime(i))
  48.                 primes.add(i);
  49.     }
  50.  
  51.     private static boolean isPrime(int n) {
  52.         if (n == 1)
  53.             return false;
  54.         if (n == 2)
  55.             return true;
  56.         if (n % 2 == 0)
  57.             return false;
  58.         for (long i = 3; i * i <= n; i += 2) {
  59.             if (n % i == 0)
  60.                 return false;
  61.         }
  62.         return true;
  63.     }
  64.  
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement