hardy_ramanujanalgo.py

# This theorem states that the number of prime factors of n
# will be approximately log(log(n)) for most natural numbers n

importmath


defexact_prime_factor_count(n: int) ->int:
"""
 >>> exact_prime_factor_count(51242183)
 3
 """
count=0
ifn%2==0:
count+=1
whilen%2==0:
n=int(n/2)
# the n input value must be odd so that
# we can skip one element (ie i += 2)

i=3

whilei<=int(math.sqrt(n)):
ifn%i==0:
count+=1
whilen%i==0:
n=int(n/i)
i=i+2

# this condition checks the prime
# number n is greater than 2

ifn>2:
count+=1
returncount


if__name__=="__main__":
n=51242183
print(f"The number of distinct prime factors is/are {exact_prime_factor_count(n)}")
print(f"The value of log(log(n)) is {math.log(math.log(n)):.4f}")

"""
 The number of distinct prime factors is/are 3
 The value of log(log(n)) is 2.8765
 """