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.

diff --git a/ginac/factor.cpp b/ginac/factor.cpp
index 0d3d4dd835a0a200224f271941b8f473f2af66c7..3b93cc6d0d04398cd6d861ca78f7b0e2c7a7aece 100644 (file)
--- 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<unsigned int> 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<n; ++i ) {
-                               if (candidate % primes[i])
-                                       continue;
-                               candidate += 2;
-                               i=-1;
-                       }
-                       primes.push_back(candidate);
-                       if (candidate > p)
+static unsigned int next_prime(unsigned int n)
+{
+       static vector<unsigned int> 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;
                }
        }