Во-первых, вы должны использовать точное арифметическое средство. Другие предложили использовать 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> или простых чисел, пока квадрат не будет равен или больше вашего целевого номера. Затем просто проверьте эту серию чисел для делимости на цель.