Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Scanner;
- public class MainClass {
- static ArrayList<Integer> primes = new ArrayList<Integer>();
- public static void main(String[] args) {
- generatePrimes(50000);
- @SuppressWarnings("resource")
- Scanner input = new Scanner(System.in);
- int num = input.nextInt();
- ArrayList<Integer> factors = factorize(num);
- System.out.print(factors.toString());
- }
- public static ArrayList<Integer> factorize(int num) {
- ArrayList<Integer> factors = new ArrayList<Integer>();
- if (isPrime(num))
- factors.add(num);
- else {
- while (num != 1) {
- for (int prime : primes) {
- while ((num % prime) == 0) {
- factors.add(prime);
- num /= prime;
- if (num == 1)
- return factors;
- }
- }
- generatePrimes(200000);
- }
- }
- return factors;
- }
- private static void generatePrimes(int limit) {
- primes.clear();
- for (int i = 2; primes.size() < limit; i++)
- if (isPrime(i))
- primes.add(i);
- }
- private static boolean isPrime(int n) {
- if (n == 1)
- return false;
- if (n == 2)
- return true;
- if (n % 2 == 0)
- return false;
- for (long i = 3; i * i <= n; i += 2) {
- if (n % i == 0)
- return false;
- }
- return true;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement