From 4fd717045b56a15ee8602dfd005d7362db738d0a Mon Sep 17 00:00:00 2001 From: Richard Kreckel Date: Thu, 22 Dec 2022 18:19:59 +0100 Subject: [PATCH] Fix internal next_prime(n) function. This helper function was doing wild things when called the wrong way. E.g. it would allocate obscene amounts of memory and run for ages when called with an argument that has never been returned by it before. In the context where it's being used so far this is not a problem. But it's better to make it foolproof and spare a new user some possible despair and distress. --- ginac/factor.cpp | 40 +++++++++++++++++----------------------- 1 file changed, 17 insertions(+), 23 deletions(-) diff --git a/ginac/factor.cpp b/ginac/factor.cpp index 0d3d4dd8..3b93cc6d 100644 --- a/ginac/factor.cpp +++ b/ginac/factor.cpp @@ -1303,35 +1303,29 @@ static void hensel_univar(const upoly& a_, unsigned int p, const umodpoly& u1_, } } -/** Returns a new prime number. +/** Returns a new small prime number. * - * @param[in] p prime number - * @return next prime number after p + * @param[in] n an integer + * @return smallest prime greater than n */ -static unsigned int next_prime(unsigned int p) -{ - static vector primes; - if (primes.empty()) { - primes = {3, 5, 7}; - } - if ( p >= primes.back() ) { - unsigned int candidate = primes.back() + 2; - while ( true ) { - size_t n = primes.size()/2; - for ( size_t i=0; i p) +static unsigned int next_prime(unsigned int n) +{ + static vector primes = {2, 3, 5, 7}; + unsigned int candidate = primes.back(); + while (primes.back() <= n) { + candidate += 2; + bool is_prime = true; + for (size_t i=1; primes[i]*primes[i]<=candidate; ++i) { + if (candidate % primes[i] == 0) { + is_prime = false; break; + } } - return candidate; + if (is_prime) + primes.push_back(candidate); } for (auto & it : primes) { - if ( it > p ) { + if ( it > n ) { return it; } } -- 2.49.0