# What’s The First Number to Have N Factors or More?

I am working on a problem where I need to find the first integer which has N or more factors, where N is provided.

My approach was to pre-generate a table using the number of factors as index, and the first integer that has that number of factors or more as value. I make the calculations using the prime numbers and multiplying them (elevated to various powers). Below is the code:

``````
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstdio>
using namespace std;

#define NFACTORS 1000000

int main(){
int primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
int expo = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
unsigned long long int factors[NFACTORS];
int tests;
int i,j,n;
int x,y,toRaise;
unsigned long long int result,numFactors,current;

for (i=0;i<NFACTORS;i++)
factors[i]=9999999999999999ULL;

factors=0;
factors=1;
factors=2;

for (x=1;x<6;x++){
expo=x;
for (y=1;y<20;y++)
expo[y]=1;
toRaise=1;
while(expo<=x){
for (i=0;i<20;i++){
result = 1;
numFactors = 1;
for (j=0;j<=i;j++){
result *= (int)pow(primes[j],expo[j]);
numFactors *= (expo[j]+1);
}
if (numFactors>=NFACTORS)
break;;
if (factors[numFactors]==9999999999999999ULL||factors[numFactors]>result)
factors[numFactors] = result;
}
if(toRaise==20)
toRaise=1;
expo[toRaise]++;
toRaise++;
}
}

/* this part is used to discover the highest number of factors found, used below
for (i=NFACTORS-1;i>=0;i--)
if (factors[i]!=9999999999999999)
cout << "First number with " << i << " factors = " << factors[i] << endl;
*/

/* clean the table of wrong and empty values */
current=factors;
for (i=995328;i>=0;i--){
if (factors[i]==9999999999999999ULL)
factors[i]=current;
else if(factors[i]>current)
factors[i]=current;
else if(factors[i]<current)
current=factors[i];
}
return 0;
}
``````

## 2 thoughts on “What’s The First Number to Have N Factors or More?”

1. Carl Sebeny

The first integer with N factors is 2^N.

2. shiva

Itz 2^(N-1)