Smallest integer which has n factors or more | Python3 program to print the smallest integer with n factors or more ; array to store prime factors ; function to generate all prime factors of numbers from 1 to 10 ^ 6 ; Initializes all the positions with their value . ; Initializes all multiples of 2 with 2 ; A modified version of Sieve of Eratosthenes to store the smallest prime factor that divides every number . ; check if it has no prime factor . ; Initializes of j starting from i * i ; if it has no prime factor before , then stores the smallest prime divisor ; function to calculate number of factors ; stores the smallest prime number that divides n ; stores the count of number of times a prime number divides n . ; reduces to the next number after prime factorization of n ; false when prime factorization is done ; if the same prime number is dividing n , then we increase the count ; if its a new prime factor that is factorizing n , then we again set c = 1 and change dup to the new prime factor , and apply the formula explained above . ; prime factorizes a number ; for the last prime factor ; function to find the smallest integer with n factors or more . ; check if no of factors is more than n or not ; generate prime factors of number upto 10 ^ 6
MAX = 100001 ; NEW_LINE factor = [ 0 ] * MAX ; NEW_LINE def generatePrimeFactors ( ) : NEW_LINE INDENT factor [ 1 ] = 1 ; NEW_LINE for i in range ( 2 , MAX ) : NEW_LINE INDENT factor [ i ] = i ; NEW_LINE DEDENT i = 4 NEW_LINE while ( i < MAX ) : NEW_LINE INDENT factor [ i ] = 2 ; NEW_LINE i += 2 ; NEW_LINE DEDENT i = 3 ; NEW_LINE while ( i * i < MAX ) : NEW_LINE INDENT if ( factor [ i ] == i ) : NEW_LINE INDENT j = i * i ; NEW_LINE while ( j < MAX ) : NEW_LINE INDENT if ( factor [ j ] == j ) : NEW_LINE INDENT factor [ j ] = i ; NEW_LINE DEDENT j += i ; NEW_LINE DEDENT DEDENT i += 1 ; NEW_LINE DEDENT DEDENT def calculateNoOFactors ( n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT ans = 1 ; NEW_LINE dup = factor [ n ] ; NEW_LINE c = 1 ; NEW_LINE j = int ( n / factor [ n ] ) ; NEW_LINE while ( j != 1 ) : NEW_LINE INDENT if ( factor [ j ] == dup ) : NEW_LINE INDENT c += 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT dup = factor [ j ] ; NEW_LINE ans = ans * ( c + 1 ) ; NEW_LINE c = 1 ; NEW_LINE DEDENT j = int ( j / factor [ j ] ) ; NEW_LINE DEDENT ans = ans * ( c + 1 ) ; NEW_LINE return ans ; NEW_LINE DEDENT def smallest ( n ) : NEW_LINE INDENT i = 1 ; NEW_LINE while ( True ) : NEW_LINE INDENT if ( calculateNoOFactors ( i ) >= n ) : NEW_LINE INDENT return i ; NEW_LINE DEDENT i += 1 ; NEW_LINE DEDENT DEDENT generatePrimeFactors ( ) ; NEW_LINE n = 4 ; NEW_LINE print ( smallest ( n ) ) ; NEW_LINE