Проблемы с простыми числами

Я пытаюсь написать программу, чтобы найти наибольший простой фактор из очень большого числа, и попробовал несколько методов с переменным успехом. Все те, что я нашел до сих пор, были невероятно медленными. У меня была мысль, и мне интересно, если это правильный подход:

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

Этот подход потребовал бы ввода и сделал бы следующее:

200 -> 100 -> 50 -> 25 -> 5 (возврат)

90 -> 45 -> 15 -> 5 (возврат)

Он многократно делит currentNum на наименьшее делимое число (чаще всего на 2 или 3) до тех пор, пока само currentNum не станет простым (нет делимого простого числа, меньшего, чем квадратный корень currentNum), и предполагает, что это наибольший простой множитель исходного ввода.

Будет ли это всегда работать? Если нет, может ли кто-нибудь дать мне контрпример?

-

РЕДАКТИРОВАТЬ: Под очень большой, я имею в виду около 2^40 или 10^11.

Источник

6 ответов

Решение

Это всегда будет работать из-за теоремы об уникальной простой факторизации.

Источник

Метод будет работать, но будет медленным. "Насколько велики твои числа?" определяет метод для использования:

Источник

Конечно, это будет работать (см. Ответ Марка Байерса), но для "очень больших" входных данных это может занять слишком много времени. Вы должны отметить, что ваш звонок getLowestDivisiblePrimeNumber() скрывает еще один цикл, так что он работает на O(N^2), и что в зависимости от того, что вы подразумеваете под "очень большим", он может работать с BigNums, что будет медленно.

Вы можете немного ускорить его, заметив, что вашему алгоритму не нужно проверять факторы, меньшие, чем последний найденный.

Источник

Вы пытаетесь найти главные факторы числа. То, что вы предлагаете, будет работать, но все равно будет медленным для большого числа... вы должны быть благодарны за это, так как большинство современных систем безопасности основаны на том, что это трудная проблема.

Источник

Из быстрого поиска, который я только что сделал, самый быстрый известный способ вычисления числа - использование метода эллиптических кривых.

Вы можете попробовать набрать свой номер на этой демонстрации: http://www.alpertron.com.ar/ECM.HTM.

Если это убедит вас, вы можете попробовать либо украсть код (это неинтересно, они предоставляют ссылку на него!), Либо ознакомиться с его теорией в другом месте. Об этом есть статья в Википедии: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization но я слишком глуп, чтобы понять это. К счастью, это твоя проблема, а не моя!:)

Источник

Особенность Project Euler заключается в том, что для решения проблемы обычно существует очевидный метод грубой силы, который будет длиться почти вечно. По мере того, как вопросы становятся более сложными, вам нужно будет реализовывать умные решения.

Одним из способов решения этой проблемы является использование цикла, который всегда находит наименьший (положительное целое) множитель числа. Когда наименьшим фактором числа является это число, то вы нашли наибольший простой фактор!

Подробное описание алгоритма:

Вы можете сделать это, сохранив три переменные:

Число, которое вы пытаетесь вычислить (A) Текущее хранилище делителей (B) Крупнейшее хранилище делителей (C)

Первоначально, пусть (A) будет число, которое вас интересует - в данном случае это 600851475143. Затем пусть (B) будет 2. Имейте условие, которое проверяет, делится ли (A) на (B). Если он делится, разделите (A) на (B), сбросьте (B) до 2 и вернитесь к проверке, делится ли (A) на (B). Иначе, если (A) не делится на (B), увеличьте (B) на +1, а затем проверьте, делится ли (A) на (B). Выполняйте цикл до тех пор, пока (A) не станет равным 1. Возвращаемое вами (3) будет наибольшим простым делителем 600851475143.

Есть множество способов сделать это более эффективным - вместо того, чтобы увеличивать до следующего целого числа, вы можете увеличивать до следующего обязательно простого целого числа, и вместо того, чтобы хранить наибольшее хранилище делителей, вы можете просто вернуть текущее число, когда его единственный делитель равен сам. Однако алгоритм, который я описал выше, будет работать в считанные секунды.

Реализация в Python выглядит следующим образом:

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

Пример. Найдем наибольший простой множитель 105, используя метод, описанный выше.

Пусть (A) = 105. (B) = 2 (мы всегда начинаем с 2), и у нас пока нет значения для (C).

Делится ли (A) на (B)? Нет. Увеличение (B) на +1: (B) = 3. Делится ли (A) на (B)? Да. (105/3 = 35). Самый большой найденный делитель - 3. Пусть (C) = 3. Обновление (A) = 35. Сброс (B) = 2.

Теперь (A) делится на (B)? Нет. Увеличить (B) на +1: (B) = 3. Делится ли (A) на (B)? Нет. Увеличить (B) на +1: (B) = 4. Делится ли (A) на (B)? Нет. Увеличение (B) на +1: (B) = 5. Делится ли (A) на (B)? Да. (35/5 = 7). Самый большой делитель, который мы нашли ранее, хранится в (С). (C) в настоящее время 3,5 больше 3, поэтому мы обновляем (C) = 5. Обновляем (A)=7. Сбрасываем (B) = 2.

Затем мы повторим процесс для (A), но мы будем продолжать увеличивать (B) до тех пор, пока (B) = (A), потому что 7 является простым и не имеет делителей, кроме себя и 1. (Мы могли бы уже остановиться, когда (B))>((A)/2), поскольку целочисленные делители не могут быть больше половины числа - наименьший возможный делитель (кроме 1) любого числа равен 2!)

Таким образом, в этот момент мы возвращаем (A)=7.

Попробуйте сделать несколько из них вручную, и вы поймете идею

Источник
Другие вопросы по тегам