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

Question

На самом деле, учитывая N a (возможно, очень большое) четное целое число, я хочу найти N = F * R, где gcd (F, R) = 1, F> R и F как можно меньше (так как I 'Я буду полностью учитывать 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 или псевдокоде.

---

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

Answer 1

В Википедии есть хороший список алгоритмов факторинга: http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms

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

Кроме того, вы можете начать с теста первичности, чтобы вы знали, что N составная, прежде чем выполнять дополнительную работу.

В вашей заметке говорится, что вы не учитываете N, но проблемы связаны. Поиск F и R сводится к изучению непересекающихся комбинаций простых множителей N .

В случае N==36 начальная факторизация N равна 2, 2, 3, 3. Коэффициенты F и R должны включать все из них (так, чтобы F*R==N), и не может быть никакого перекрытия (так, чтобы GCD(F,R)==1). Таким образом, 4 и 9 появляются немедленно.

Более поучительным примером может быть N==23256. Его факторизация 2,2,2,3,3,17,19. Поскольку не может быть перекрытия между F и R , каждая первичная база может входить только в одно из двух ведер (т.е. вы либо получаете все два, либо ни одного из них). Таким образом, мы можем сгруппировать факторы в 8,9,17,19. Чтобы найти R, мы хотим, чтобы комбинация этих факторов была как можно большей, но ниже 152,49, квадратный корень из 23256. Наш выбор: {8}, {9}, {8,9}, {8,17} , {8,19}. Самый большой из них - 8*19, что составляет 152. Соответствующее F равно 17*19 или 153.

варианты , перечисленные выше, вычисляются как [choice for choice in powerset([8,9,17,19]) if prod(choice) < math.sqrt(N)].

Таким образом, вся программа сводится к следующему:

prime_factors = factorize(N)      # [2,2,2,3,3,17,19]
clusters = [p**e for p, e in collections.Counter(prime_factors).items()]  # [8,9,17,19]
R = max(prod(group) for group in powerset(clusters) if prod(group) < math.sqrt(N))
F = N // R

Поиск powerset можно ускорить, обрезав генерацию наборов всякий раз, когда они превышают квадратный корень в N .

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

Answer 2

def factor_partial(N):
    R = int(sqrt(float(N)))
    sieve = [1, 1] + [0] * (R-1)
    for i in xrange(2, R) :
        if sieve[i]==0 :
            j=i*i;
            while j<=R :
                sieve[j]=1
                j = j + i
    primes = [i for i in xrange(R+1) if sieve[i]==0]

    saveN = N
    primepower_divisors = []
    for i in primes :
        if N%i == 0 :
            term = 1
            while N%i == 0 :
                term = term * i
                N = N / i
            primepower_divisors = primepower_divisors + [term]
            if N==1 : break

    largecoprime_divisors = [1]
    for i in primepower_divisors :
        for j in largecoprime_divisors :
            largecoprime_divisors = largecoprime_divisors + [i*j]

    F = min([i for i in largecoprime_divisors if i>R])
    return F, saveN/F

Я использовал метод sieve для вычисления списка простых чисел (при вычислении списка простых чисел возможны многие оптимизации) Мы могли бы использовать тот факт, что .. не будет простого числа p, такого что F% p == 0 и R% p == 0.поскольку gcd (F, R) = 1

Answer 3

Не могли бы вы получить простую факторизацию N, а затем найти наибольшую комбинацию продуктов из всех простых факторов, которая меньше, чем sqrt (N)?

Например, с 36 он обнаружит, что основная факторизация2 * 2 * 3 * 3.Затем вы попробуете все различные комбинации простых чисел:

2 = 2
3 = 3
2 * 2 = 4
2 * 3 = 6
3 * 3 =9
2 * 2 * 3 = 12
2 * 3 * 3 = 18
2 * 2 * 3 * 3 = 36

И вы знаете, что это все факторыиз 36, так что вы найдете самый большой такой, что он меньше, чем sqrt (36), который оказывается 4.

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

Но даже тогда (возвращаясь к первой восторженной версии) O (sqrt (n)) довольно быстрое время выполнения и требует только O (1) памяти, так что на самом деле первый алгоритм может быть просто способомидти.Я не вижу, как это будет медленно, особенно в C на современном компьютере.