Найти наибольший делитель N, который меньше sqrt(N)

На самом деле, учитывая N - (возможно, очень большое) четное целое число, я хочу найти N = F * R, где gcd(F,R) = 1, F>R, и F как можно меньше (поскольку я буду полностью факторизовать F). Суть проблемы заключается в нахождении наибольшего делителя R, при котором R

Например, N=36 должно дать F=9 и R=4. Обратите внимание, что R не обязательно простое или простое число. Обратите внимание, что я НЕ факторизую N. Единственное ограничение на F и R - это то, что они относительно простые.

Это моя быстрая и наивная версия, которая работает:

def factor_partial(N):
    for R in xrange(int(math.sqrt(N)),1,-1):
        if N%R == 0 and gcd(R,N/R) == 1:
            return N/R, R

Другой способ, который я представляю, это найти делители в порядке возрастания и удалить все кратные неделимые по пути. Что-то вроде:

def factor_partial(N):
    i = range(2, int(sqrt(N)) + 1)
    while i:
        if N % i[0] != 0:
            remove_multiples(i, i[0]) #without removing i[0]
        else:
            if gcd(i[0], N/i[0]) == 1:
                R = i[0]
        i.pop(0) #remove i[0]

    return N/R, R

Я думаю, это будет медленно и потребует много памяти, но, возможно, если i вместо генератора, это может быть эффективно. Я не часто использовал генераторы.

Можно ли улучшить первую версию? Является ли вторая версия жизнеспособной (как бы я это сделал)? Есть ли совершенно другой метод, который лучше?

Ищу ответы в python, c или псевдокоде.

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