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[20] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
    int expo[20] = {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]=0;
    factors[1]=1;
    factors[2]=2;

    for (x=1;x<6;x++){
        expo[0]=x;
        for (y=1;y<20;y++)
            expo[y]=1;
        toRaise=1;
        while(expo[1]<=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[995328];
    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?

Leave a Reply

Your email address will not be published. Required fields are marked *