Question

Find the smallest positive integer that has precisely n distinct prime divisors. 'Distinct prime divisor'Example: the prime factorization of 8 is 2 * 2 * 2, so it has one distinct prime divisor. Another: the prime factorization of 12 is 2 * 2 * 3, so it has two distinct prime divisors. A third: 30 = 2 * 3 * 5, which gives it three distinct prime divisors. (n = 24 ⇒ 23768741896345550770650537601358310. From this you conclude that you cannot iterate through successive positive integers until you find the one you want. Use Python.

Answer 1

Checking for each and every integer , factorizing them and verifying them if they have n distinct prime divisors is very time consuming.The optimized is to avoid this approach and follow the below logic

The logic here is to find the n prime numbers and multiply them.

The smallest positive integer that has precisely n distinct prime divisors will hold the following properties :

1 . It will not have any repeated divisor (No single divisor repeats twice)

2 . It is formed by prime numbers multiplied in the ascending order

EX : smallest positive integer that has precisely 3 distinct prime divisors would be

30 = 2 * 3 * 5 where 2 ,3 , 5 are the first 3 prime numbers

6 = 2*3 , 6 is the smallest positive integer that has 2 distinct prime divisors

How Did I find Prime Numbers ?

I have used wilson's theorem to find the prime numbers

According to wilson theorem , if p is prime number then ((p-1)!+1)%p must be equal to 0

ex : 5 is prime

(5-1)!+1 = 4!+1

= 24 + 1

= 25

25%5 = 0

hence 5 is prime.

CODE :

#Calculate the given n no. of primes
def primes(n) :
prime = []
k=2
f = 1
while n>0 :
f = f * (k - 1)
if ((f + 1) % k == 0):
prime.append(k)
n = n-1
k = k+1
return prime

#Take the input
n = input("Enter the n value\n")
#Get n primes
p = primes(int(n))
ans = 1
#Multiply all primes until n
for i in p:
ans = ans * i
print("Smallest +ve integer that has precisely",n," distinct prime divisors :")
print(ans)

Spyder (Python 3.7) Eile Edit Searh So un Debug Consales Projects Tools View Help Vereble explorer roject explorer mppy X webrawlenpy X prima.pyX NameType Size 1 # -*. coding: utf-8-* int 1 30 3 Created on Tue May 21 00:9:03 2019 Bauthor: Rogue int 1 6#Calculate the given n no. of primes 7 def prines(n) 8 prine list 3 12, 3. 5 1 f 1 11 ile ne: 12 if((f t 1) % k-6): prime.append(k) n = n-1 Verieble explarer Fils aspicrar Help 14 Pytron consolc 16 17 return prine 18 19#Tale the input 20input("Cniter the n valuetn") 21 #Get n primes p pritn)) Enter the n value mallest ve integer that has precisely 4 distinct prine divisars 210 23 ans-1 24#Multiply all primes until n 5for i in p: In L10]: runtile'C:Users/Rague/Desktap/prine.py,wdir-'C:/Users/Rague Desktop) 26 2/ print( "Snallest we integer that has precisely",n," distinct prine divisors ") 28 print(ans) Enter the n valur 24. Snallest ave integer that has preciscly 24 distinct prine divisors 23768741896345558770650537601358310 In [11]: runileC/Users/Rogue/Desktop/prine, py,wdir-'C:/Users/Rogue Desktop') Enter the n valuc Smallestve integer that has precisely 3 distinct prine divisors 38 In [12]: Python cornele History og Permissicns: RW End-af-lines: CRLF Enpdin: UIF-B Line:28 Column: 11 Memory: 62% 1222 AM O Typc here to searc 5/21/20159

Enter the n value 4 Smallest tve integer that has precisely 4 distinct prime divisors: 210 In [10] runfile('C:/Users/Rogue/Desktop/prime.py', wdir-'C:/Users/Rogue Desktop") Enter the n value 244 Smallest +ve integer that has precisely 24 distinct prime divisors 23768741896345550770650537601358310 In [11]: runfile('C:/Users/Rogue/Desktop/prime.py', wdir-'C:/Users/Rogue/ Desktop') Enter the n value Smallest +ve integer that has precisely 3 distinct prime divisors 30 In [121: