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++)


    for (x=1;x<6;x++){
        for (y=1;y<20;y++)
            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)
                if (factors[numFactors]==9999999999999999ULL||factors[numFactors]>result)
                    factors[numFactors] = result;

    /* 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 */
    for (i=995328;i>=0;i--){
        if (factors[i]==9999999999999999ULL)
        else if(factors[i]>current)
        else if(factors[i]<current)
    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 *