Почему этот алгоритм разложения на простые множители дал правильный ответ даже при наличии изъяна?

Обратите внимание, что в алгоритме есть 3 недостатка:

1. 2 также простое число
2. Он может делить числа, не являющиеся простыми, и нечетные (например, 9)
3. Он НЕ делит простое число более одного раза (как и следовало ожидать для таких чисел, как 27).

Из них мы можем сделать вывод, что неработающий алгоритм даст правильный ответ, если выполняются 2 следующих условия:

1. Номер входа нечетный (поэтому переход на 2 не имеет значения)
2. Пусть число будет n = p1*p2*...*p_k, где p_i - все простые числа. Для каждого j!=i: p_i != p_j. Здесь это означает, что на самом деле каждое простое число является множителем входного числа только один раз, и, таким образом, проблемы 2 + 3 «избегаются». (Проблема 2 - это тривиально, почему ее избегают, проблемы 3 избегают, потому что вы уже разделили число со всеми соответствующими простыми множителями, поэтому для каждого m=p_i1*...*p_ic, поскольку число уже было разделено на все простые множители - p_i1,...p_ic - вы не сможете разделить это с m.

Поскольку все говорят вам, что не так с вашей программой, я дам правильный алгоритм факторизации целых чисел с использованием пробного деления:

function factors(n)
    f, fs := 2, []
    while f * f <= n
        if n % f == 0
            append f to fs
            n := n / f
        else f := f + 1
    append n to fs
    return fs

Это решает две проблемы с вашим кодом. Во-первых, он правильно определяет факторы 2. Во-вторых, он возвращает все факторы с их множественностью.

Чтобы ответить на ваш вопрос о делении на не простые числа: это проблема производительности, а не проблема правильности. Поскольку пробные делители проверяются в возрастающем порядке, любые составные делители уже будут удалены из факторизуемого числа при проверке составляющих их простых чисел. Это означает, что деление на составное бесполезно, но на результат это не повлияет.

И, конечно, никогда не следует использовать арифметику с плавающей запятой при работе с целыми числами. В C, когда вы выходите за рамки длинных длинных целых чисел, вы, вероятно, захотите переключиться на библиотеку gmp.

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

Это работает, потому что в вашем номере нет повторяющихся факторов.

600851475143 = 71 * 839 * 1471 * 6857

Попробуйте, например, 1573499 (23 * 37 * 43 * 43).

Если проверяемое число четное, программа будет работать вечно. x всегда будет четным, y всегда будет нечетным, поэтому x == y никогда не будет истинным.

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

Интересен случай, когда в проверяемом числе есть множители, представляющие собой квадраты, кубы и т. Д. Нечетных простых чисел. Цикл найдет нечетные простые множители и разделит на них, но, например, если 3 ^ 2 - множитель, он будет делиться на 3, оставляя множитель 3. Что именно происходит, зависит от простых множителей. Если есть только один простой квадратный множитель p ^ 2, программа не завершится. Если есть куб или два квадрата (p ^ 3 или p ^ 2 q ^ 2), результатом будет неправильный оставшийся множитель p ^ 2 или pq, если только число не имеет большего простого множителя, чем это.

Пример: 3 ^ 2 x 5 ^ 2 x 13: находятся множители 3, 5 и 13, затем выводится 15, что неверно. Пример: 3 ^ 2 x 5 ^ 2 x 17: находятся множители 3, 5 и 15, затем печатается 17, что оказывается правильным.