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

Question

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

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.

Answer 1

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

Answer 2

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

• Менее 2^16 или около того:Справочная таблица.
• Менее 2^70 или около того: Сито Аткина.Это оптимизированная версия более известного Решето Эратосфена. Редактировать: Модификация Ричарда Брента из Ро-алгоритм Полларда может быть лучше в этом случае.
• Менее 10^50: Факторизация эллиптической кривой Ленстры
• Менее 10^100: Квадратичное сито
• Более 10^100: Общее числовое поле сита

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

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

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

Число, которое вы пытаетесь учитывать (а) текущий магазин Divisor (B) крупнейший магазин Divisor (C)

Изначально пусть (А) будет интересующим вас числом — в данном случае это 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, используя метод, описанный выше.

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

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

Делится ли (А) на (В)?Нет.Увеличение (B) на +1:(Б) = 3.Делится ли (А) на (В)?Нет.Увеличение (B) на +1:(Б) = 4.Делится ли (А) на (В)?Нет.Увеличение (B) на +1:(Б) = 5.Делится ли (А) на (В)?Да.(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.

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