Smallest integer which has n factors or more | c ++ 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 ; Driver program to test above function ; generate prime factors of number upto 10 ^ 6
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1000001 ; int factor [ MAX ] = { 0 } ; void generatePrimeFactors ( ) { factor [ 1 ] = 1 ; for ( int i = 2 ; i < MAX ; i ++ ) factor [ i ] = i ; for ( int i = 4 ; i < MAX ; i += 2 ) factor [ i ] = 2 ; for ( int i = 3 ; i * i < MAX ; i ++ ) { if ( factor [ i ] == i ) { for ( int j = i * i ; j < MAX ; j += i ) { if ( factor [ j ] == j ) factor [ j ] = i ; } } } } int calculateNoOFactors ( int n ) { if ( n == 1 ) return 1 ; int ans = 1 ; int dup = factor [ n ] ; int c = 1 ; int j = n / factor [ n ] ; while ( j != 1 ) { if ( factor [ j ] == dup ) c += 1 ; else { dup = factor [ j ] ; ans = ans * ( c + 1 ) ; c = 1 ; } j = j / factor [ j ] ; } ans = ans * ( c + 1 ) ; return ans ; } int smallest ( int n ) { for ( int i = 1 ; ; i ++ ) if ( calculateNoOFactors ( i ) >= n ) return i ; } int main ( ) { generatePrimeFactors ( ) ; int n = 4 ; cout << smallest ( n ) ; return 0 ; }