Garmaine Staff asked 2 years ago

I've written the following C++ code to factorize really large numbers efficiently (numbers up to 24997300729). I have a vector containing 41000 primes approx.( I know having such a large vector isn't a good idea although but couldn't figure a way around this). This code produces the prime factorization of moderately large numbers in no time but when it comes to numbers such as, 24997300572 the program stalls.

Here's the program below with some screenshots of the output:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>

using namespace std;

vector<int> primes = {paste from  

   https://drive.google.com/file/d/1nGvtMMQSa9YIDkMW2jgEbJk67P7p54ft/view?usp=sharing
};

void factorize(int n) {
    if (n == 1)
        return;
    if (find(primes.begin(), primes.end(), n) != primes.end()) {
        cout << n <<" ";            //if n is prime dont'proceed further
        return;
    }

    //obtaining an iterator to the location of prime equal to or just greater than sqrt(n)
    auto s = sqrt(n);
    vector<int>::iterator it = lower_bound(primes.begin(), primes.end(), s);

    if (it == primes.end()) {
        return;                 // if no primes found then the factors are beyond range
    }
    for (auto i = it;i != primes.begin();i--) {
        if (n % *i == 0)
        {
            cout << *i << " ";
            n = n / (*i);
            factorize(n);
            return;             // the two consecutive for() loops should never run one after another
        }

    }
    for (auto i = it;i != primes.end();i++) {
        if (n % *i == 0)
        {
            cout << *i << " ";
            n = n / (*i);
            factorize(n);
            return;         // the two consecutive for() loops should never run one after another
        }
    }
}

int main() {
    unsigned int n;
    cout << "Enter a number between 1 and 24997300729 ";
    cin >> n;
    if (n > 24997300729) {
        cout << "Number out of range;";
        exit(-1);
    }
    factorize(n);
    return 0;
}

This is OK

This is Ok

But This is NOT!!!

But This is NOT

I tried using long long int and long double wherever I could to over come the problem of large numbers, but that didn't help much.

Any help Would Be Greatly Appreciated