Первичная факторизация – список

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

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

Мой код:

 def primes(n): primfac = [] d = 2 while (n > 1): if n%d==0: primfac.append(d) # how do I continue from here... ? 

  • Установить opencv для Python 3.3
  • Как читать входы как целые числа?
  • Ошибка Python3: «Ошибка импорта: нет имени модуля urllib2»
  • isinstance не выводит ничего
  • Могу ли я использовать ProcessPoolExecutor из будущего?
  • Почему я получаю int при индексировании байтов?
  • Как использовать conda для создания отдельных сред python, каждый из которых имеет разные $ PYTHONPATH
  • Блокировка байтов (не строк) в Python 2 и 3
  • 13 Solutions collect form web for “Первичная факторизация – список”

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

     def primes(n): primfac = [] d = 2 while d*d <= n: while (n % d) == 0: primfac.append(d) # supposing you want multiple factors repeated n //= d d += 1 if n > 1: primfac.append(n) return primfac 

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

    Это решение на основе понимания, оно может быть самым близким к рекурсивному решению на Python, которое можно использовать для больших чисел.

    Вы можете получить правильные делители с одной строкой:

     divisors = [ d for d in xrange(2,int(math.sqrt(n)) if n % d == 0 ] 

    то мы можем проверить, чтобы число в дивизорах было простым:

     def isprime(d): return all( d % od != 0 for od in divisors if od != d ) 

    который проверяет, что никакие другие делители не делят d.

    Затем мы можем фильтровать простые делители:

     prime_divisors = [ d for d in divisors if isprime(d) ] 

    Конечно, его можно объединить в одну функцию:

     def primes(n): divisors = [ d for d in range(2,n//2+1) if n % d == 0 ] return [ d for d in divisors if \ all( d % od != 0 for od in divisors if od != d ) ] 

    Здесь \ находится там, чтобы разбить строку, не вступая в отладку Python.

    Модуль premfac делает факторизации со всеми математическими причудливыми методами, разработанными на протяжении веков:

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

    Большинство вышеупомянутых решений выглядят несколько неполными. Первичная факторизация повторила бы каждый простой коэффициент числа (eg 9 = [3 3]) .

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

    Использование sieve Of Eratosthenes для поиска простых образцов для тестирования является оптимальным, но; вышеупомянутая реализация использовала больше памяти, чем необходимо.

    Я не уверен, что если "wheel factorization" будет превосходить применение только простых факторов, для тестов деления n.

    Хотя это решение действительно полезно, я бы предложил следующие две функции –

    Функция-1:

     def primes(n): if n < 2: return yield 2 plist = [2] for i in range(3,n): test = True for j in plist: if j>n**0.5: break if i%j==0: test = False break if test: plist.append(i) yield i 

    Функция-2:

     def pfactors(n): for p in primes(n): while n%p==0: yield p n=n//p if n==1: return list(pfactors(99999)) [3, 3, 41, 271] 3*3*41*271 99999 list(pfactors(13290059)) [3119, 4261] 3119*4261 13290059 
     def get_prime_factors(number): """ Return prime factor list for a given number number - an integer number Example: get_prime_factors(8) --> [2, 2, 2]. """ if number == 1: return [] # We have to begin with 2 instead of 1 or 0 # to avoid the calls infinite or the division by 0 for i in xrange(2, number): # Get remainder and quotient rd, qt = divmod(number, i) if not qt: # if equal to zero return [i] + get_prime_factors(rd) return [number] 

    Я изменил ответ @ user448810 на использование итераторов из itertools (и python3.4, но он должен быть обратно переносимым). Решение на 15% быстрее.

     import itertools def factors(n): f = 2 increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6])) for incr in increments: if f*f > n: break while n % f == 0: yield f n //= f f += incr if n > 1: yield n 

    Обратите внимание, что это возвращает итерабельность, а не список. Оберните его в список (), если это то, что вы хотите.

    простые множители числа:

     def primefactors(x): factorlist=[] loop=2 while loop<=x: if x%loop==0: x//=loop factorlist.append(loop) else: loop+=1 return factorlist x = int(input()) alist=primefactors(x) print(alist) 

    Вы получите список. Если вы хотите получить пары простых факторов числа, попробуйте это: http://pythonplanet.blogspot.in/2015/09/list-of-all-unique-pairs-of-prime.html

    Вы можете использовать сито Эратосфена для генерации всех простых чисел до (n/2) + 1 а затем использовать понимание списка, чтобы получить все основные факторы:

     def rwh_primes2(n): # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188 """ Input n>=6, Returns a list of primes, 2 <= p < n """ correction = (n%6>1) n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6] sieve = [True] * (n/3) sieve[0] = False for i in xrange(int(n**0.5)/3+1): if sieve[i]: k=3*i+1|1 sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1) sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1) return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]] def primeFacs(n): primes = rwh_primes2((n/2)+1) return [x for x in primes if n%x == 0] print primeFacs(99999) #[3, 41, 271] 

    Вот моя версия факторизации путем пробного деления, которая включает в себя оптимизацию деления только на два и нечетные целые числа, предложенные Даниэлем Фишером:

     def factors(n): f, fs = 3, [] while n % 2 == 0: fs.append(2) n /= 2 while f * f <= n: while n % f == 0: fs.append(f) n /= f f += 2 if n > 1: fs.append(n) return fs 

    Улучшение пробного деления на два и нечетные числа – это факторизация колес , которая использует циклический набор разрывов между потенциальными числами, чтобы значительно уменьшить количество пробных подразделений. Здесь мы используем 2,3,5-колесо:

     def factors(n): gaps = [1,2,2,4,2,4,2,4,6,2,6] length, cycle = 11, 3 f, fs, next = 2, [], 0 while f * f <= n: while n % f == 0: fs.append(f) n /= f f += gaps[next] next += 1 if next == length: next = cycle if n > 1: fs.append(n) return fs 

    Таким образом, будут выдаваться print factors(13290059) [3119, 4261] . Факторинговые колеса имеют одинаковую сложность времени O (sqrt (n)) как обычное пробное деление, но на практике в два-три раза быстрее.

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

      from sets import Set # this function generates all the possible factors of a required number x def factors_mult(X): L = [] [L.append(i) for i in range(2,X) if X % i == 0] return L # this function generates list containing prime numbers upto the required number x def prime_range(X): l = [2] for i in range(3,X+1): for j in range(2,i): if i % j == 0: break else: l.append(i) return l # This function computes the intersection of the two lists by invoking Set from the sets module def prime_factors(X): y = Set(prime_range(X)) z = Set(factors_mult(X)) k = list(y & z) k = sorted(k) print "The prime factors of " + str(X) + " is ", k # for eg prime_factors(356) 

    Большая часть ответа усложняет ситуацию. Мы можем сделать это

     def prime_factors(n): num = [] #add 2 to list or prime factors and remove all even numbers(like sieve of ertosthenes) while(n%2 == 0): num.append(2) n /= 2 #divide by odd numbers and remove all of their multiples increment by 2 if no perfectlly devides add it for i in xrange(3, int(sqrt(n))+1, 2): while (n%i == 0): num.append(i) n /= i #if no is > 2 ie no is a prime number that is only divisible by itself add it if n>2: num.append(n) print (num) 

    Алгоритм от GeeksforGeeks

    Простой способ получить желаемое решение

     def Factor(n): d = 2 factors = [] while n >= d*d: if n % d == 0: n//=d # print(d,end = " ") factors.append(d) else: d = d+1 if n>1: # print(int(n)) factors.append(n) return factors 
     def factorize(n): for f in range(2,n//2+1): while n%f == 0: n //= f yield f 

    Это медленно, но мертво просто. Если вы хотите создать служебную программу командной строки, вы можете сделать следующее:

     import sys [print(i) for i in factorize(int(sys.argv[1]))] 
    Python - лучший язык программирования в мире.