CODEWITHSUNDEEP
c++loopsinfinite-loopprimes
user3178285
user3178285

Reputation: 151

Infinite loop happening somewhere here?

I'm writing a program to estimate the percentage of non-negative integers that are prime. The following code somehow produces an infinite loop, as my output is saying "Timeout" on the online compiler I'm using. However, I can't figure out what part of the code is producing the issue. It looks pretty straight-forward to me.

#include <iostream> 

bool isPrime(unsigned long L) { 
    if (L < 3) { 
        return true; 
    } else { 
        unsigned long i = 2;
        while (i < L)
           if (L % i++ == 0)
                return false;
    }
    return true;
}

int main() { 

    unsigned long k = 0;
    unsigned long N = ~k;
    unsigned long count = 0;
    while (k++ < N)  
        if (isPrime(k)) 
            ++count;

    long double percentPrime = count / N;
    std::cout << "Percentage of prime numbers from 0 to " << N << " = " << percentPrime;

    return 0;
}

Upvotes: 0

Views: 130

Answers (4)

Zac Howland
Zac Howland

Reputation: 15872

First off, your loop is not infinite. It will run until it reaches 0xFFFFFFFF, which will take forever.

Part of the reason it will take forever is you are using what amounts to an O(N^2) algorithm (so it will take 0xFFFFFFFF * 0xFFFFFFFF operations to finish).

You should use a sieve, or at the very least, optimize your is_prime function:

bool is_prime(unsigned int i, const std::deque<unsigned int>& previous_primes)
{
    std::size_t j = 0;
    while (previous_primes[j] * previous_primes[j] <= i)
    {
        if (i % previous_primes[j] == 0)
            return false;
        ++j;
    }
    return true;
}

And your main code would then be:

// initialize some known primes
std::deque<unsigned int> primes;
primes.push_back(2);
primes.push_back(3);
primes.push_back(5);
primes.push_back(7);

for (unsigned int i = 9; i <= 0xFFFFFFFF; i += 2)
{
    if (is_prime(i, primes))
    {
        primes.push_back(i);
    }
}

// your percentage of primes would be (mathematically) primes.size() / 0xFFFFFFFF

Note that because of the iterations, this will still take forever to loop through all odd integers from 9 to 0xFFFFFFFF.

Side Note

Effectively, you are writing a program to show the following simple proof:

  • Start with 2, so the percentage of primes must be less than .5, as every other number is divisible by 2.
  • Next, 3, so the percentage of primes must be less than .33 as every 3rd number is divisible by 3.
  • Next 5 ...

As the primes get larger and larger, the maximum percentage becomes 1/some infinite prime ~= 0. (the limit of f(x) = 1/x as x approaches infinity is 0).

So here, the mathematical proof is much faster than your attempt at a programmatic proof.

Upvotes: 2

barak manos
barak manos

Reputation: 30136

Not infinite, just extremely long.

It would have been infinite if you had written while (k++ <= N) instead of while (k++ < N)...

BTW, 1 is generally not considered a prime number, but your code yields that it is.

P.S.: If you want a rough estimation of the percentage of primes in the range 1...N, then you can simply do the following math instead: 100/log(N), where log(N) is the natural logarithm of N.

Upvotes: 1

prmottajr
prmottajr

Reputation: 1824

It doesn't seems to be infinite, but since it is very long and time consuming it is timingout.

What I suggest is to improve your primality test with some tricks:

1 - you only need to test the number until its square root (sqrt(L))

2 - you only need to test odd numbers for primality (so you can start to try to divide the number by 3 and increase the test by 2, so you will test against 3,5,7,9,etc...)

Cheers

Upvotes: 1

Eric Fortin
Eric Fortin

Reputation: 7603

unsigned long k = 0;
unsigned long N = ~k;

Here N will be 0xFFFFFFFF which is a really big number so the loop is not infinite but long.

Upvotes: 1

Related Questions