Smallest integer which has n factors or more | PHP 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
< ? php $ MAX = 100001 ; $ factor = array_fill ( 0 , $ MAX , 0 ) ; function generatePrimeFactors ( ) { global $ MAX ; global $ factor ; $ factor [ 1 ] = 1 ; for ( $ i = 2 ; $ i < $ MAX ; $ i ++ ) $ factor [ $ i ] = $ i ; for ( $ i = 4 ; $ i < $ MAX ; $ i += 2 ) $ factor [ $ i ] = 2 ; for ( $ i = 3 ; $ i * $ i < $ MAX ; $ i ++ ) { if ( $ factor [ $ i ] == $ i ) { for ( $ j = $ i * $ i ; $ j < $ MAX ; $ j += $ i ) { if ( $ factor [ $ j ] == $ j ) $ factor [ $ j ] = $ i ; } } } } function calculateNoOFactors ( $ n ) { global $ factor ; if ( $ n == 1 ) return 1 ; $ ans = 1 ; $ dup = $ factor [ $ n ] ; $ c = 1 ; $ j = ( int ) ( $ n / $ factor [ $ n ] ) ; while ( $ j != 1 ) { if ( $ factor [ $ j ] == $ dup ) $ c += 1 ; else { $ dup = $ factor [ $ j ] ; $ ans = $ ans * ( $ c + 1 ) ; $ c = 1 ; } $ j = ( int ) ( $ j / $ factor [ $ j ] ) ; } $ ans = $ ans * ( $ c + 1 ) ; return $ ans ; } function smallest ( $ n ) { for ( $ i = 1 ; ; $ i ++ ) if ( calculateNoOFactors ( $ i ) >= $ n ) return $ i ; } generatePrimeFactors ( ) ; $ n = 4 ; echo smallest ( $ n ) ; ? >