Python - подсчитать количество простых делителей без использования диапазона - PullRequest
Новая
       8

Python - подсчитать количество простых делителей без использования диапазона

0 голосов
/ 26 января 2020

Мне нужно написать функцию, которая подсчитывает общее число простых делителей заданного натурального числа n. Поскольку я только начал изучать python в неделю go, мне не разрешено использовать l oop с диапазоном. Ниже приведено то, что у меня есть: 

def count_prime_divisors(n):
    return num_of_divisors(n, 1)

def num_of_divisors(n, i):
    if i > n:
        return 0
    if n % i == 0 and num_of_divisors(i, 1) == 2:
        return 1 + num_of_divisors(n, i+1)
    else:
        return num_of_divisors(n, i+1)

Итак, я знаю, что в этой строке возникает ошибка превышения максимальной глубины рекурсии if n % i == 0 and num_of_divisors(i, 1) == 2, но я не знаю, как проверить, является ли делитель простым, чтобы функция может работать соответствующим образом. Может быть, я должен написать другую вспомогательную функцию? Может кто-то помочь мне с этим? Любая помощь очень ценится :( Спасибо!

Ответы [ 2 ]

0 голосов
/ 26 января 2020

если вы используете Linux, это должно работать (без циклов, без диапазонов, без ничего =): 

>>> import os
>>> 
>>> def factor(num) :
...     output = os.popen( 'factor %d' % num ).read()
...     return map( int, output.split(':')[-1].split())
... 
>>> print factor(128)
[2, 2, 2, 2, 2, 2, 2]
>>>

Я надеюсь, вы знаете, как взять длину списка, используя len()

0 голосов
/ 26 января 2020

Вы можете попробовать это. 

def prime_fac(n,count=0,prime_num=2):
    if n==1:
        print('Number of prime factors',count)
        return
    elif n%prime_num==0:
        print(prime_num)
        return prime_fac(n//prime_num,count+1,prime_num)
    else:
        return prime_fac(n,count,prime_num+1)

prime_fac(100)
prime_fac(12)
prime_fac(999)

output 

2
2
5
5
Number of prime factors 4
2
2
3
Number of prime factors 3
3
3
3
37
Number of prime factors 4

Используйте это, если хотите сохранить count простых факторов и уникальные простые множители . 

def prime_fac(n,count=0,prime_num=2,prime_set=set()):
    if n==1:
        print('Number of prime factors',count)
        return count,prime_set
    elif n%prime_num==0:
        print(prime_num)
        prime_set=prime_set|{prime_num}  #set union operation
        return prime_fac(n//prime_num,count+1,prime_num,prime_set)
    else:
        return prime_fac(n,count,prime_num+1,prime_set)

a=prime_fac(100)
print(a)

выход 

2
2
5
5
Number of prime factors 4

(4, {2, 5}) #a looks like this where 4 is prime factors count and {2,5} is unique prime factors.
...