Number which has the maximum number of distinct prime factors in the range M to N in Python
In this article, we have a task to find and print the number which has the maximum amount of distinct prime factors between the given range M and N in Python. If there are multiple numbers falling in that criteria then print the smallest one. Let there be two numbers M and N given as input by the user. Now, we have to find the smallest number in the range M and N that has the maximum number of distinct prime factors.
A number is prime when it is divisible by 1 and itself only eg, 3,5,7,11,13 and so on. Note: 1 is not a prime number and 2 is the only even prime number. No even numbers are prime.
Now for this task, I have divided the code into three functions for better understanding and simplicity:
- prime– This function checks whether a given number is prime or not.
#function to check if the number is prime or not def prime(x): c=0 for i in range(1,x): if x%i==0: c+=1 if c==1: return True #returns True if prime return False #return False if composite
Let’s call the function for distinct values-
print(f"{5} is prime?",prime(5)) print(f"{6} is prime?",prime(6)) print(f"{1} is prime?",prime(1)) print(f"{2} is prime?",prime(2))
Output:
5 is prime? True 6 is prime? False 1 is prime? False 2 is prime? True
- factors– This function checks and returns the total number of distinct prime factors for any given integer.
def factors(i): l=[] for x in range(1,i+1): if i%x==0: pr=prime(x) #calling the above prime function if pr==True and pr not in l: l.append(x) #appends all the distinct prime factors of an integer return len(l) #calculates the length of the total number of distinct prime factors
Let’s check the total number of distinct prime factors for various distinct integers:
print(f"{4} has",factors(4),"distinct prime factors") print(f"{5} has",factors(5),"distinct prime factors") print(f"{6} has",factors(6),"distinct prime factors") print(f"{7} has",factors(7),"distinct prime factors") print(f"{8} has",factors(8),"distinct prime factors") print(f"{9} has",factors(9),"distinct prime factors") print(f"{10} has",factors(10),"distinct prime factors")
Output-
4 has 1 distinct prime factors 5 has 1 distinct prime factors 6 has 2 distinct prime factors 7 has 1 distinct prime factors 8 has 1 distinct prime factors 9 has 1 distinct prime factors 10 has 2 distinct prime factors
- maximum– This is the final function which keeps a check of the number which has the maximum number of distinct prime factors between the given range and keeps updating it. Finally, it returns the output. This function takes the input range numbers (M, N) as arguments
#the main function to begin the program between m and n range def maximum(m,n): lar=0 #to store the largest number of distinct primes at any time #largest number num=0 for i in range(m,n+1): cal_factors=factors(i) #number of calculated distinct prime factors if cal_factors>lar: lar=cal_factors num=i return num
Let’s test the final output for two sets of inputs (4,10) & (100,150):
print(f"smallest number between 4 and 10 with maximum distinct prime factors is: ",maximum(4,10)) print(f"smallest number between 100 and 105 with maximum distinct prime factors is: ",maximum(100,105))
Output-
smallest number between 4 and 10 with maximum distinct prime factors is: 6 smallest number between 100 and 105 with maximum distinct prime factors is: 102
Leave a Reply