Prime Factor Problem Time Limit

Question

Input: The only integer (N<=10^9): 999999937
Output: Each line contains its respective prime and exponent divisors. The prime factors areexported in ascending order: 999999937 1

When I try this test case, it takes some times to run and display output (on some compilers, it shows time limit or time out). How to fix that?

import java.util.Scanner;

public class Factor {

public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
int n, count, m = 0;

System.out.print("Enter number: ");
n = keyboard.nextInt();

n = Math.abs(n);
count = 0;

for (int i = 2; i <= n; i++) {
while (n % i == 0) {
if (n % i == 0) {
count++;
m = i;
}
n = n / i;
}
if (m != 0 && count != 0) {
if (n % i != 0) {
System.out.printf("%d %d\n", m, count);
count = 0;
m = 0;
}
}
}
}
}

Answer 1

Well on Sololearn I tried your code and it ran successfully without timeout.

I don't really get why you need the m variable, you could just use i instead.

This is only a question of style, but if you give more meaningful names to your variables, it would be easier to follow the code.

You are not really taking into account the fact that we are looking for PRIME factors. You test all numbers from 2 to (potentially) n.
Maybe determining the primes up to n, for example with sieve algorithm, could make your factorisation loop faster, but there is clearly a trade-off here if you can do a quick enough algo to determine primes.

You might also try BigInteger built-in methods to get the next prime number.

Answer 2

Immediately what catches the eye is unnecessary operations.

Maximum input: 999999999.

for (int i = 2; i <= n; i++) {
if (n % i == 0) {
count++;
m = i;
n = n / i;
}
if (m != 0 && count != 0 && n % i != 0) {
System.out.printf("%d %d\n", m, count);
count = 0;
m = 0;
}
}