Это конкретно не решает все проблемы в вашем алгоритме, но может дать некоторые рекомендации. Ваше заданное число должно учитываться очень быстро, так как его основные факторы очень близки по величине. Это ускоряет процесс, поскольку целевое число уменьшается быстрее при обнаружении других факторов.
Рассмотрим следующие примеры. Первое значение - ваше, следующее - намного больше, а третье - наименьшее (и последнее по причине).
Вывод выглядит следующим образом: Фактически, это ваш номер. Часть adding - это новый фактор, часть continuing - это то, что остается после деления на этот фактор и что подлежит дальнейшей факторизации. Значения в скобках являются найденными факторами для данного числа.
Checking: 600851475143
Adding 71, continuing with 8462696833
Adding 839, continuing with 10086647
Adding 1471, continuing with 6857
Adding 6857, continuing with 1
[71, 839, 1471, 6857]
В результате первые два числа вычисляются очень быстро. Третий займет много времени. Это потому, что он прост, и используя этот метод, я должен был бы сгенерировать все простые числа до этого значения, чтобы проверить этот факт. Таким образом, не размер является единственным фактором (предназначенным для каламбура), это относительная величина основных факторов.
Вот процедура теста.
for (long test : new long[] { 600851475143L,
14385829455476874L, 300851475157L }) {
System.out.println();
System.out.println("Checking: " + test);
List<Long> factors = findFactors(test);
System.out.println(factors);
}
static private int lastReturnedPrimeIdx = 0;
static private List<Long> primes = new ArrayList<>(
List.of(2L, 3L));
// find all prime factors in a supplied number.
public static List<Long> findFactors(long n) {
List<Long> factors = new ArrayList<>();
lastReturnedPrimeIdx = 0;
while (n > 1) {
long p = nextPrime();
while (n % p == 0) {
factors.add(p);
n /= p;
System.out.println("Adding " + p
+ ", continuing with " + n);
}
}
return factors;
}
// Get the next prime. This memoizes the primes as they are computed.
// Future tests on the same run can thus take advantage of the cached values.
// Prime are computed in bulk.
private static long nextPrime() {
if (lastReturnedPrimeIdx < primes.size()) {
return primes.get(lastReturnedPrimeIdx++);
}
// start where the it left off last time.
long candidate = primes
.get(lastReturnedPrimeIdx - 1);
long max = primes.size() + 1_000; // generate 1000 more primes.
outer:
while (primes.size() < max) {
candidate += 2;
long bound = (long)Math.sqrt(candidate);
for (int i = 0; i < primes.size(); i++) {
long p = primes.get(i);
if (candidate % p == 0 ) {
continue outer;
}
if (p > bound) {
break;
}
}
primes.add(candidate);
}
return (primes.get(lastReturnedPrimeIdx++));
}
}
Последнее замечание: я рекомендую вычислять простые числа будущих кандидатов по формуле:
- Деление только кандидатов на уже найденные простые числа .
- Проверка только нечетных кандидатов после 2.
- Проверка только
primes до квадрата root кандидата.
Другой вариант - Сито Эратосфена