有没有办法在C ++中分解大数

It's a little unclear (at least to me) exactly why you've structured the program the way you have.

You can fully factor a number by only looking for prime factors less than or equal to that number's square root. Any prime factor larger than those pairs with one prime factors smaller than that, so you only have to search for those to find all the prime factors. Any remaining factors can be obtained by simple division, not searching.

I'd probably generate the base of prime numbers on the fly (mostly likely using a sieve). The square root of 24'997'300'729 is (about) 158'105. A quick test shows that even without any work on optimization, a sieve of Eratosthenes will find the primes up to that limit in about 12 milliseconds.

Personally, I'd rather not have a fixed limit on the largest number the user can factor, other than the limit on the size of number we're working with, so if the user enters something close to the limit for a 64-bit number, we find all the primes that fit in 32 bits, and then use those to factor the number. This will obviously be slower than if we don't find as many primes, but a user probably won't be too surprised at the idea that factoring a larger number takes longer than factoring a smaller number.

So, implementing that, we might end up with code something like this:

#include <iostream>
#include <locale>
#include <vector>
#include <string>

using Number = unsigned long long;

auto build_base(Number limit) {
    std::vector<bool> sieve(limit / 2, true);

    for (Number i = 3; i < limit; i += 2) {
        if (sieve[i / 2]) {
            for (Number temp = i * i; temp < limit; temp += i)
                if (temp & 1)
                    sieve[temp / 2] = false;
        }
    }
    return sieve;
}

void factor(Number input, std::vector<bool> const &candidates)
{
    while (input % 2 == 0) {
        std::cout << 2 << "\t";
        input /= 2;
    }

    for (Number i = 1; i < candidates.size(); i++) {
        if (candidates[i]) {
            auto candidate = i * 2 + 1;
            while ((input % candidate) == 0) {
                    std::cout << candidate << "\t";
                    input /= candidate;
            }
        }
    }
    if (input != 1)
        std::cout << input;
}

int main(int argc, char **argv) {
    std::cout.imbue(std::locale(""));

    if (argc != 2) {
        std::cerr << "Usage: factor <number>\n";
        return EXIT_FAILURE;
    }

    auto number = std::stoull(argv[1]);
    auto limit = std::sqrt(number) + 1;
    auto candidates = build_base(limit);

    factor(number, candidates);
}

At a high level, the code works like this: we start by finding the primes up to the square root of the number the user entered. Since we want all the primes up to a limit, we use a sieve of Eratosthenes to find them. This builds a vector of bools, in which vector[n] will be true if n is prime, and false if n is composite. It does this starting from 3 (2 is a special case we kind of ignore for now) and crossing off the multiples of three. Then it finds the next number that hasn't been crossed off (which will be five, in this case), and crosses off its multiples. It continues doing that until it reaches the end of the array. To save some space, it leaves all the even numbers out of the array, because (other than that special case for 2) we already know none of them is prime.

一旦有了这些，我们就可以使用这些质数来找到要分解的数的质因数。这非常简单：遍历素数向量，并测试每个素数是否均分到目标数。如果是这样，请打印出来，将其除以目标编号，然后继续。

至少对我来说，这似乎相当可靠，并且速度相当快。如果我们想更好地分解较大的数字，那么下一步将是切换到分段筛。这可以极大地提高工作的第一部分的速度，例如，使我们（例如）可以在不超过约10秒的时间内分解出适合64位数字的任何内容。