Python Поиск основных факторов

Ответ 1

Этот вопрос был первой ссылкой, которая появилась, когда я googled "python prime factorization". Как указано в @quangpn88, этот алгоритм неверен (!) Для идеальных квадратов, таких как n = 4, 9, 16, ... Однако, также не работает @quangpn88 fix, так как оно даст неверные результаты, если наибольший простой коэффициент возникает 3 или более раз, например, n = 2*2*2 = 8 или n = 2*3*3*3 = 54.

Я считаю, что правильный алгоритм грубой силы в Python:

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Не используйте это в коде производительности, но это нормально для быстрых тестов с умеренно большими номерами:

In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 µs per loop

Если выполняется полная простая факторизация, это алгоритм грубой силы:

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

Ответ 2

Ok. Итак, вы сказали, что понимаете основы, но вы не совсем точно знаете, как это работает. Прежде всего, это отличный ответ на вопрос проекта Эйлера, из которого он вытекает. Я много исследовал эту проблему, и это самый простой ответ.

В целях объяснения я дам n = 20. Чтобы запустить реальную проблему Project Euler, давайте n = 600851475143.

n = 20 
i = 2

while i * i < n:
    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

В этом объяснении используются две петли while. Самое главное помнить о циклах while - это то, что они запускаются, пока они больше не будут true.

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

Внутренний цикл утверждает, что, пока i равномерно делит на n, замените n на n, деленный на i. Этот цикл работает непрерывно до тех пор, пока он перестанет быть истинным. Для n=20 и i=2, n заменяется на 10, а затем на 5. Поскольку 2 не равномерно разделяется на 5, цикл останавливается с n=5, а внешний цикл заканчивается, создавая i+1=3.

Наконец, поскольку квадрат 3 больше, чем 5, внешний цикл больше не true и печатает результат n.

Спасибо, что опубликовали это. Я посмотрел на код навсегда, прежде чем понять, как именно он работает. Надеюсь, это то, что вы ищете в ответ. Если нет, сообщите мне, и я могу объяснить далее.

Ответ 3

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

#!python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))

Ответ 4

Для генерации простых чисел я всегда использую Sieve of Eratosthenes:

def primes(n):
    if n<=2:
        return []
    sieve=[True]*(n+1)
    for x in range(3,int(n**0.5)+1,2):
        for y in range(3,(n//x)+1,2):
            sieve[(x*y)]=False

    return [2]+[i for i in range(3,n,2) if sieve[i]]

In [42]: %timeit primes(10**5)
10 loops, best of 3: 60.4 ms per loop

In [43]: %timeit primes(10**6)
1 loops, best of 3: 1.01 s per loop

Вы можете использовать тест простоты Миллера-Рабина, чтобы проверить, является ли число простым или нет. Вы можете найти его реализации Python здесь.

Всегда используйте модуль timeit для определения времени вашего кода, второй - только 15us:

def func():
    n = 600851475143
    i = 2
    while i * i < n:
         while n % i == 0:
            n = n / i
         i = i + 1

In [19]: %timeit func()
1000 loops, best of 3: 1.35 ms per loop

def func():
    i=1
    while i<100:i+=1
   ....:     

In [21]: %timeit func()
10000 loops, best of 3: 15.3 us per loop

Ответ 5

Не самый большой простой коэффициент 27 равен 3?? Вышеуказанный код может быть самым быстрым, но он не работает 27 правильно? 27 = 3 * 3 * 3 Вышеприведенный код возвращает 1 Насколько я знаю..... 1 не является ни простым, ни композитным

Я думаю, это лучший код

def prime_factors(n):
    factors=[]
    d=2
    while(d*d<=n):
        while(n>1):            
            while n%d==0:
                factors.append(d)
                n=n/d
            d+=1
    return factors[-1]

Ответ 6

Код неправильный с 100. Он должен проверить регистр я * я = n:

Я думаю, что это должно быть:

while i * i <= n:
    if i * i = n:
        n = i
        break

    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

Ответ 7

Другой способ сделать это:

import sys
n = int(sys.argv[1])
result = []
for i in xrange(2,n):
    while n % i == 0:
        #print i,"|",n
        n = n/i
        result.append(i)

    if n == 1: 
        break

if n > 1: result.append(n)
print result

вывод проб:
python test.py 68
[2, 2, 17]

Ответ 8

"""
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

"""

from sympy import primefactors
print primefactors(600851475143)[-1]

Ответ 9

def find_prime_facs(n):
  list_of_factors=[]
  i=2
  while n>1:
    if n%i==0:
      list_of_factors.append(i)
      n=n/i
      i=i-1
    i+=1  
  return list_of_factors

Ответ 10

Мой код:

# METHOD: PRIME FACTORS
def prime_factors(n):
    '''PRIME FACTORS: generates a list of prime factors for the number given
    RETURNS: number(being factored), list(prime factors), count(how many loops to find factors, for optimization)
    '''
    num = n                         #number at the end
    count = 0                       #optimization (to count iterations)
    index = 0                       #index (to test)
    t = [2, 3, 5, 7]                #list (to test)
    f = []                          #prime factors list
    while t[index] ** 2 <= n:
        count += 1                  #increment (how many loops to find factors)
        if len(t) == (index + 1):
            t.append(t[-2] + 6)     #extend test list (as much as needed) [2, 3, 5, 7, 11, 13...]
        if n % t[index]:            #if 0 does else (otherwise increments, or try next t[index])
            index += 1              #increment index
        else:
            n = n // t[index]       #drop max number we are testing... (this should drastically shorten the loops)
            f.append(t[index])      #append factor to list
    if n > 1:
        f.append(n)                 #add last factor...
    return num, f, f'count optimization: {count}'

Который я сравнил с кодом с большинством голосов, который был очень быстрым

    def prime_factors2(n):
        i = 2
        factors = []
        count = 0                           #added to test optimization
        while i * i <= n:
            count += 1                      #added to test optimization
            if n % i:
                i += 1
            else:
                n //= i
                factors.append(i)
        if n > 1:
            factors.append(n)
        return factors, f'count: {count}'   #print with (count added)

ТЕСТИРОВАНИЕ (обратите внимание, я добавил COUNT в каждом цикле, чтобы проверить оптимизацию)

# >>> prime_factors2(600851475143)
# ([71, 839, 1471, 6857], 'count: 1472')
# >>> prime_factors(600851475143)
# (600851475143, [71, 839, 1471, 6857], 'count optimization: 494')

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

Ответ 11

Если вы хотите использовать здесь numpy, способ создать массив всех простых чисел, не превышающих n:

[ я for я in np.arange(2,n+1) if 0 not in np.array([i] * (i-2) ) % np.arange(2,i)]

Ответ 12

Проверьте это, это может немного помочь вам в вашем понимании.

#program to find the prime factors of a given number
import sympy as smp

try:
    number = int(input('Enter a number : '))
except(ValueError) :
    print('Please enter an integer !')
num = number
prime_factors = []
if smp.isprime(number) :
    prime_factors.append(number)
else :
    for i in range(2, int(number/2) + 1) :   
        """while figuring out prime factors of a given number, n
        keep in mind that a number can itself be prime or if not, 
        then all its prime factors will be less than or equal to its int(n/2 + 1)"""
        if smp.isprime(i) and number % i == 0 :
            while(number % i == 0) :
                prime_factors.append(i)
                number = number  / i
print('prime factors of ' + str(num) + ' - ')
for i in prime_factors :
    print(i, end = ' ')

Ответ 13

Ниже приведены два способа эффективной генерации простых факторов заданного числа:

from math import sqrt


def prime_factors(num):
    '''
    This function collectes all prime factors of given number and prints them.
    '''
    prime_factors_list = []
    while num % 2 == 0:
        prime_factors_list.append(2)
        num /= 2
    for i in range(3, int(sqrt(num))+1, 2):
        if num % i == 0:
            prime_factors_list.append(i)
            num /= i
    if num > 2:
        prime_factors_list.append(int(num))
    print(sorted(prime_factors_list))


val = int(input('Enter number:'))
prime_factors(val)


def prime_factors_generator(num):
    '''
    This function creates a generator for prime factors of given number and generates the factors until user asks for them.
    It handles StopIteration if generator exhausted.
    '''
    while num % 2 == 0:
        yield 2
        num /= 2
    for i in range(3, int(sqrt(num))+1, 2):
        if num % i == 0:
            yield i
            num /= i
    if num > 2:
        yield int(num)


val = int(input('Enter number:'))
prime_gen = prime_factors_generator(val)
while True:
    try:
        print(next(prime_gen))
    except StopIteration:
        print('Generator exhausted...')
        break
    else:
        flag = input('Do you want next prime factor ? "y" or "n":')
        if flag == 'y':
            continue
        elif flag == 'n':
            break
        else:
            print('Please try again and enter a correct choice i.e. either y or n')

Ответ 14

Алгоритм Python ниже использует небольшое количество теории чисел; увидеть

Правда ли, что все простые числа имеют вид 6m + 1 и 6m - 1?

а также

Корень квадратный корень из n

Вот код Python. Программа заняла минуту или около того, чтобы фактор

18.014.398.241.046.527

простое число.

def factor_out_prime(k,m):
    r = 0
    exp = 0
    while r == 0:
        xxfactored, r = divmod(m, k)
        if r == 0:
            exp = exp + 1
            m = xxfactored
        else:
            if exp > 0:
                factorization_seq.append( (k, exp) )
    if xxfactored < k and m > 1:
        factorization_seq.append( (m, 1) )
        m = 1
    return m


while True:
    num = int(input('Integer to be factored = '))
    if num == 0:
        raise SystemExit
    factorization_seq = []    
    m = num
    m = factor_out_prime(2,m)
    if m > 1:
        m = factor_out_prime(3,m)
    if m > 1:
        k = 6
        while True:
            m = factor_out_prime(k - 1, m)
            if m == 1:
                break
            m = factor_out_prime(k + 1, m)
            if m == 1:
                break
            k = k + 6

* ВЫХОД *

Integer to be factored = 3
Done 3 = [(3, 1)]
Integer to be factored = 100
Done 100 = [(2, 2), (5, 2)]
Integer to be factored = 600851475143
Done 600851475143 = [(71, 1), (839, 1), (1471, 1), (6857, 1)]
Integer to be factored = 12345678901234567890
Done 12345678901234567890 = [(2, 1), (3, 2), (5, 1), (101, 1), (3541, 1), (3607, 1), (3803, 1), (27961, 1)]
Integer to be factored = 68718952447
Done 68718952447 = [(68718952447, 1)]
Integer to be factored = 18014398241046527
Done 18014398241046527 = [(18014398241046527, 1)]
Integer to be factored = 0
>>>

Ответ 15

Вы не должны зацикливаться до квадратного корня из числа! Это может быть правильным несколько раз, но не всегда!

Наибольший простой коэффициент 10 равен 5, что больше, чем sqrt (10) (3,16, aprox).

Наибольший простой коэффициент 33 равен 11, что больше, чем sqrt (33) (5.5,74, aprox).

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

Ответ 16

Выполните следующие действия:

def primefactors(n):
  return filter(lambda x:n%x==0, range(2, int(floor(sqrt(n)))))

Ответ 17

def prime(n):
    for i in range(2,n):
        if n%i==0:
            return False
    return True

def primefactors():
    m=int(input('enter the number:'))
    for i in range(2,m):
        if (prime(i)):
            if m%i==0:
                print(i)
    return print('end of it')

primefactors()

Ответ 18

Другой способ, который пропускает четные числа после обработки 2:

def prime_factors(n):
   factors = []
   d    = 2
   step = 1
   while d*d <= n:
      while n>1:
         while n%d == 0:
            factors.append(d)
            n = n/d
        d += step
        step = 2

  return factors

Ответ 19

n=int(input("Enter the number"))
if n==1 :  #because the below logic doesn't work on 1
    print(n)
for i in range(2 , n+1):
    if n%i==0 :
        n1=i  #get factor
        for b in range(2,n+1): #check if it is prime
            if ((n1%b)==0) & (n1==b):
                print(n1)
            elif (n1%b)==0 or n1<b:  #if not then pass
                break

Я уверен, что это худшая логика, но все знания у меня есть .py эта программа получит номер от пользователя и распечатает все это число чисел, которые являются главными, как за 12, это даст 2,3