Во-первых, вы должны использовать точные арифметические средства. Другие предложили использовать BigInteger. Вы можете сделать это. Для меня это немного похоже на читерство (это будет более важно для последующих задач, связанных с гораздо большими целыми числами), поэтому более забавный способ (imho) - написать необходимые операции произвольной точности самостоятельно.
Во-вторых, 600851475143 достаточно мал, чтобы быть точным с long, что будет намного быстрее.
В-третьих, ваш цикл неправильно проверяет основные факторы. Вы просто проверяете нечетные числа. Это базовое (неполное) решение:
long num = 600851475143L;
List<Long> factors = new ArrayList<Long>(); // or use a Set
if (num & 1 == 0) {
factors.add(2L);
}
for (long i=3; i*i<=num; i+=2) {
// first check i is prime
// if i is prime check if it is a factor of num
}
Проверка, является ли что-то простое, имеет разные уровни реализации. Самые наивные:
public boolean isPrime(long num) {
for (long i=2; i<=num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
Конечно, это делает все виды ненужной проверки. Как вы уже определили, вам нужно только проверить числа до sqrt(n), и вы можете удалить четные числа (кроме 2):
public boolean isPrime(long num) {
if (num & 1 == 0) {
return false; // checks divisibility by 2
}
for (long i=3; i*i<=num; i+=2) {
if (num % i == 0) {
return false;
}
}
return true;
}
Но вы тоже можете добиться большего. Другая оптимизация заключается в том, что вам нужно проверять число только по простым числам в этом диапазоне. Основными множителями 63 являются 3 и 7. Если число не делится на 3 или 7, то оно по определению не делится на 63.
Итак, вы хотите построить, вероятно, Set<Long> или простые числа, пока квадрат не станет равным или больше, чем ваше целевое число. Затем просто проверьте эту серию чисел на делимость на цель.