# include < iostream >
# include < cmath >
# include < limits >
using namespace std ;
const int MAX_N = 1001 ;
const int PRIME_COUNT = 169 ;
int prime[] = { 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 , 211 , 223 , 227 , 229 , 233 , 239 , 241 , 251 , 257 , 263 , 269 , 271 , 277 , 281 , 283 , 293 , 307 , 311 , 313 , 317 , 331 , 337 , 347 , 349 , 353 , 359 , 367 , 373 , 379 , 383 , 389 , 397 , 401 , 409 , 419 , 421 , 431 , 433 , 439 , 443 , 449 , 457 , 461 , 463 , 467 , 479 , 487 , 491 , 499 , 503 , 509 , 521 , 523 , 541 , 547 , 557 , 563 , 569 , 571 , 577 , 587 , 593 , 599 , 601 , 607 , 613 , 617 , 619 , 631 , 641 , 643 , 647 , 653 , 659 , 661 , 673 , 677 , 683 , 691 , 701 , 709 , 719 , 727 , 733 , 739 , 743 , 751 , 757 , 761 , 769 , 773 , 787 , 797 , 809 , 811 , 821 , 823 , 827 , 829 , 839 , 853 , 857 , 859 , 863 , 877 , 881 , 883 , 887 , 907 , 911 , 919 , 929 , 937 , 941 , 947 , 953 , 967 , 971 , 977 , 983 , 991 , 997 };
long long dp [MAX_N][PRIME_COUNT];
long long getMinNumberWithNDivisors ( int n, int index, long long currentNumber ) {
if (n == 1 ) {
return currentNumber ;
}
if (index >= PRIME_COUNT || currentNumber >= dp [n][index]) {
return numeric_limits < long long >:: max ();
}
if ( dp [n][index] != numeric_limits < long long >:: max ()) {
return dp [n][index];
}
long long minNumber = getMinNumberWithNDivisors (n, index + 1 , currentNumber );
long long p = prime[index];
int count = 0 ;
while (n % (( count + 1 ) * ( count + 1 )) == 0 ) { currentNumber *= p;
count ++;
long long newMin = getMinNumberWithNDivisors (n / ( count + 1 ), index + 1 , currentNumber );
if ( newMin < minNumber ) {
minNumber = newMin ;
}
}
dp [n][index] = minNumber ;
return minNumber ;
}
int main () {
int n;
cout << " Introduceti numarul n: " ;
cin >> n;
for ( int i = 0 ; i < MAX_N; i++) {
for ( int j = 0 ; j < PRIME_COUNT; j++) {
dp [i][j] = numeric_limits < long long >:: max ();
}
}
long long minNumber = getMinNumberWithNDivisors (n, 0 , 1 );
cout << "Cel mai mic numar cu " << n << " divizori este: " << minNumber << endl ;
return 0 ;
}