Что лучший способ состоит в том, чтобы получить все делители числа?
NullPointerException s - исключения, возникающие при попытке использовать ссылку, которая указывает на отсутствие местоположения в памяти (null), как если бы она ссылалась на объект. Вызов метода по нулевой ссылке или попытка получить доступ к полю нулевой ссылки вызовет функцию NullPointerException. Они наиболее распространены, но другие способы перечислены на странице NullPointerException javadoc.
Вероятно, самый быстрый пример кода, который я мог бы придумать для иллюстрации NullPointerException, be:
public class Example {
public static void main(String[] args) {
Object obj = null;
obj.hashCode();
}
}
В первой строке внутри main я явно устанавливаю ссылку Object obj равной null. Это означает, что у меня есть ссылка, но она не указывает на какой-либо объект. После этого я пытаюсь обработать ссылку так, как если бы она указывала на объект, вызывая метод на нем. Это приводит к NullPointerException, потому что нет кода для выполнения в местоположении, на которое указывает ссылка.
(Это техничность, но я думаю, что она упоминает: ссылка, которая указывает на null, равна 't то же, что и указатель C, указывающий на недопустимую ячейку памяти. Нулевой указатель буквально не указывает на в любом месте , который отличается от указаний на местоположение, которое оказывается недопустимым.)
3 ответа
Учитывая Вашу функцию factorGenerator, вот divisorGen, который должен работать:
def divisorGen(n):
factors = list(factorGenerator(n))
nfactors = len(factors)
f = [0] * nfactors
while True:
yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
i = 0
while True:
f[i] += 1
if f[i] <= factors[i][1]:
break
f[i] = 0
i += 1
if i >= nfactors:
return
полная эффективность этого алгоритма будет зависеть полностью от эффективности factorGenerator.
Мне нравится решение Greg, но мне жаль, что это не было больше Python как. Я чувствую, что это было бы быстрее и более читаемым; так через какое-то время кодирования я выпустил это.
первые две функции необходимы для создания декартова произведения списков. И может быть снова использован whnever, эта проблема возникает. Между прочим, я должен был программировать это сам, если кто-либо знает о стандартном решении для этой проблемы, не стесняйтесь связываться со мной.
"Factorgenerator" теперь возвращает словарь. И затем словарь питается в "делители", кто использует его для генерации сначала списка списков, где каждый список является списком факторов формы p^n с p началом. Тогда мы делаем декартово произведение тех списков, и мы наконец используем Greg' решение генерировать делитель. Мы сортируем их и возвращаем их.
я протестировал его, и это, кажется, немного быстрее, чем предыдущая версия. Я протестировал его как часть большей программы, таким образом, я не могу действительно сказать сколько стоит быстрее все же.
Pietro Speroni (pietrosperoni отмечают точкой его)
from math import sqrt
##############################################################
### cartesian product of lists ##################################
##############################################################
def appendEs2Sequences(sequences,es):
result=[]
if not sequences:
for e in es:
result.append([e])
else:
for e in es:
result+=[seq+[e] for seq in sequences]
return result
def cartesianproduct(lists):
"""
given a list of lists,
returns all the possible combinations taking one element from each list
The list does not have to be of equal length
"""
return reduce(appendEs2Sequences,lists,[])
##############################################################
### prime factors of a natural ##################################
##############################################################
def primefactors(n):
'''lists prime factors, from greatest to smallest'''
i = 2
while i<=sqrt(n):
if n%i==0:
l = primefactors(n/i)
l.append(i)
return l
i+=1
return [n] # n is prime
##############################################################
### factorization of a natural ##################################
##############################################################
def factorGenerator(n):
p = primefactors(n)
factors={}
for p1 in p:
try:
factors[p1]+=1
except KeyError:
factors[p1]=1
return factors
def divisors(n):
factors = factorGenerator(n)
divisors=[]
listexponents=[map(lambda x:k**x,range(0,factors[k]+1)) for k in factors.keys()]
listfactors=cartesianproduct(listexponents)
for f in listfactors:
divisors.append(reduce(lambda x, y: x*y, f, 1))
divisors.sort()
return divisors
print divisors(60668796879)
P.S. это - первый раз, когда я отправляю на stackoverflow. Я ожидаю к любой обратной связи.
Чтобы подробно остановиться, что заявил Shimi, необходимо только выполнять цикл от 1 до квадратного корня n. Затем для нахождения пары сделайте n / i, и это покроет целое пространство задач.
, Как был также отмечен, это - NP или 'трудная' проблема. Исчерпывающий поиск, способ, которым Вы делаете его, почти так хорош, как это добирается для гарантируемых ответов. Этот факт используется алгоритмами шифрования и т.п., чтобы помочь защитить их. Если кто-то должен был решить эту проблему, большинство, если не вся наша текущая 'безопасная' коммуникация будет представлена небезопасная.
код Python:
import math
def divisorGenerator(n):
large_divisors = []
for i in xrange(1, int(math.sqrt(n) + 1)):
if n % i == 0:
yield i
if i*i != n:
large_divisors.append(n / i)
for divisor in reversed(large_divisors):
yield divisor
print list(divisorGenerator(100))
, Который должен произвести список как:
[1, 2, 4, 5, 10, 20, 25, 50, 100]