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:

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-

Hence, the output is verified.
The final assembled code comprising of all the there’s functions is also provided below-

#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

#checks the number of distinct prime factors for any given number
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

#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

Thank you. I hope it helps.

Number which has the maximum number of distinct prime factors in the range M to N in Python

Leave a Reply Cancel reply

Related Posts