Прайм факторизация - список
Я пытаюсь реализовать функцию 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... ?
16 ответов
Простое пробное разделение:
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 (или в специальном случае более мелкие простые числа и циклы с меньшим числом возможных делителей).
Модуль primefac выполняет факторизации со всеми причудливыми техниками, разработанными математиками на протяжении веков:
#!python
import primefac
import sys
n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))
Это решение, основанное на понимании, оно может быть ближе всего к рекурсивному решению в 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.
Вот моя версия факторизации методом пробного деления, которая включает в себя оптимизацию деления только на два и нечетные целые числа, предложенные Даниэлем Фишером:
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, nxt = 2, [], 0
while f * f <= n:
while n % f == 0:
fs.append(f)
n /= f
f += gaps[nxt]
nxt += 1
if nxt == length:
nxt = cycle
if n > 1: fs.append(n)
return fs
Таким образом, print factors(13290059) будет выводить [3119, 4261], Факторинг-колеса имеют ту же сложность времени O(sqrt(n)), что и обычное пробное деление, но на практике они будут в два-три раза быстрее.
Я проделал большую работу с простыми числами в своем блоге. Пожалуйста, не стесняйтесь посетить и учиться.
Я подправил ответ @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
Обратите внимание, что это возвращает итеративный, а не список. Оберните его в list(), если вы этого хотите.
Большинство из приведенных выше решений выглядят несколько неполными. Простая факторизация будет повторять каждый главный фактор числа (e.g. 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]
Вот эффективный способ выполнить то, что вам нужно:
def prime_factors(n):
l = []
if n < 2: return l
if n&1==0:
l.append(2)
while n&1==0: n>>=1
i = 3
m = int(math.sqrt(n))+1
while i < m:
if n%i==0:
l.append(i)
while n%i==0: n//=i
i+= 2
m = int(math.sqrt(n))+1
if n>2: l.append(n)
return l
prime_factors(198765430488765430290) = [2, 3, 5, 7, 11, 13, 19, 23, 3607, 3803, 52579]
Большинство ответов делают вещи слишком сложными. Мы можем это сделать
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 i.e no is a prime number that is only divisible by itself add it
if n>2:
num.append(n)
print (num)
Алгоритм от GeeksforGeeks
Основные факторы ряда:
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
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]))]
Вы можете использовать сито Эратосфена для генерации всех простых чисел до (n/2) + 1 а затем использовать понимание списка, чтобы получить все основные факторы:
def rwh_primes2(n):
# http://stackru.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]
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 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 prime_factors(num, dd=2):
while dd <= num and num>1:
if num % dd == 0:
num //= dd
yield dd
dd +=1
Многие из приведенных выше ответов не подходят для небольших простых чисел, например, 3, 5 и 7. Вышеприведенные краткие и достаточно быстрые для обычного использования.
распечатать список (prime_factors (3))
[3]
Это код, который я сделал. Он отлично работает для чисел с небольшими простыми числами, но это занимает некоторое время для чисел с простыми числами в миллионах.
def pfactor(num):
div = 2
pflist = []
while div <= num:
if num % div == 0:
pflist.append(div)
num /= div
else:
div += 1
# The stuff afterwards is just to convert the list of primes into an expression
pfex = ''
for item in list(set(pflist)):
pfex += str(item) + '^' + str(pflist.count(item)) + ' * '
pfex = pfex[0:-3]
return pfex
Я хотел бы поделиться своим кодом для нахождения основных факторов числа с учетом ввода пользователем:
a = int(input("Enter a number: "))
def prime(a):
b = list()
i = 1
while i<=a:
if a%i ==0 and i!=1 and i!=a:
b.append(i)
i+=1
return b
c = list()
for x in prime(a):
if len(prime(x)) == 0:
c.append(x)
print(c)