Skip to main content
Code Review

Return to Answer

Fixed typo, improved wording
Source Link
AJNeufeld
AJNeufeld
  • 34k
  • 5
  • 39
  • 101

The std::vector<> is a dynamically sized container. For the The allocation strategy is implementation dependent, but for sake of the argument, assume the .capacity() of a std::vector<> starts off at 1 and doubles each time the vector's size exceeds the current capacity. This capacity increase requires a reallocation of storage, and possibly a copying of the entire array contents to a new location. If you are generating 1 trillion primes, you'll need 40 reallocations and will have done 1 trillion number copies over the course of the 40 reallocations. This is wasting time. If the operating system gets involved with virtual memory paging, you are going to suck up a lot more time.

If you let this loop run over night, or even over a fort-night, will this loop ever end? No! i will overflow the long long and become negative, and slowingslowly increment back towards positive numbers and repeat. Forever is not long enough. Use, at the very least, i > 0 as the loop test condition.

A long long has at least 64 bits. A double has only a 52 bit mantissa. This means when you pass a large long long to sqrt( ), you will end up losing a few bits of precision, which can make your sqrt() return slightly the wrong value. When you test sqrt(i) <= primes[j], if i is greater than 2^52, and is a perfect square, you might return a value slightly less than the correct value and fail to test the last prime value, and erroneously declare the perfect square a prime number.

The std::vector<> is a dynamically sized container. For the sake of the argument, assume the .capacity() of a std::vector<> starts off at 1 and doubles each time the vector's size exceeds the current capacity. This capacity increase requires a reallocation of storage, and possibly a copying of the entire array contents to a new location. If you are generating 1 trillion primes, you'll need 40 reallocations and will have done 1 trillion number copies over the course of the 40 reallocations. This is wasting time. If the operating system gets involved with virtual memory paging, you are going to suck up a lot more time.

If you let this loop run over night, or even over a fort-night, will this loop ever end? No! i will overflow the long long and become negative, and slowing increment back towards positive numbers and repeat. Forever is not long enough. Use i > 0 as the loop test condition.

A long long has at least 64 bits. A double has only a 52 bit mantissa. This means when you pass a large long long to sqrt( ), you will end up losing a few bits, which can make your sqrt() return slightly the wrong value. When you test sqrt(i) <= primes[j], if i is greater than 2^52, and is a perfect square, you might return a value slightly less than the correct value and fail to test the last prime value, and erroneously declare the perfect square a prime number.

The std::vector<> is a dynamically sized container. The allocation strategy is implementation dependent, but for sake of the argument, assume the .capacity() of a std::vector<> starts off at 1 and doubles each time the vector's size exceeds the current capacity. This capacity increase requires a reallocation of storage, and possibly a copying of the entire array contents to a new location. If you are generating 1 trillion primes, you'll need 40 reallocations and will have done 1 trillion number copies over the course of the 40 reallocations. This is wasting time. If the operating system gets involved with virtual memory paging, you are going to suck up a lot more time.

If you let this loop run over night, or even over a fort-night, will this loop ever end? No! i will overflow the long long and become negative, and slowly increment back towards positive numbers and repeat. Forever is not long enough. Use, at the very least, i > 0 as the loop test condition.

A long long has at least 64 bits. A double has only a 52 bit mantissa. This means when you pass a large long long to sqrt( ), you will end up losing a few bits of precision, which can make your sqrt() return slightly the wrong value. When you test sqrt(i) <= primes[j], if i is greater than 2^52, and is a perfect square, you might return a value slightly less than the correct value and fail to test the last prime value, and erroneously declare the perfect square a prime number.

Allocation strategy is unspecified in standard
Source Link
AJNeufeld
AJNeufeld
  • 34k
  • 5
  • 39
  • 101

The std::vector<> is a dynamically sized container. For the sake of the argument, assume the .capacity() of a std::vector<> starts off at 1 and doubles each time the vector's size will exceedexceeds the current capacity. This capacity increase requires a reallocation of storage, and possibly a copying of the entire array contents to a new location. If you are generating 1 trillion primes, you'll need 40 reallocations and will have done 1 trillion number copies over the course of the 40 reallocations. This is wasting time. If the operating system gets involved with virtual memory paging, you are going to suck up a lot more time.

The .capacity() of a std::vector<> starts off at 1 and doubles each time the vector's size will exceed the current capacity. This capacity increase requires a reallocation of storage, and possibly a copying of the entire array contents to a new location. If you are generating 1 trillion primes, you'll need 40 reallocations and will have done 1 trillion number copies over the course of the 40 reallocations. This is wasting time. If the operating system gets involved with virtual memory paging, you are going to suck up a lot more time.

The std::vector<> is a dynamically sized container. For the sake of the argument, assume the .capacity() of a std::vector<> starts off at 1 and doubles each time the vector's size exceeds the current capacity. This capacity increase requires a reallocation of storage, and possibly a copying of the entire array contents to a new location. If you are generating 1 trillion primes, you'll need 40 reallocations and will have done 1 trillion number copies over the course of the 40 reallocations. This is wasting time. If the operating system gets involved with virtual memory paging, you are going to suck up a lot more time.

Source Link
AJNeufeld
AJNeufeld
  • 34k
  • 5
  • 39
  • 101

The .capacity() of a std::vector<> starts off at 1 and doubles each time the vector's size will exceed the current capacity. This capacity increase requires a reallocation of storage, and possibly a copying of the entire array contents to a new location. If you are generating 1 trillion primes, you'll need 40 reallocations and will have done 1 trillion number copies over the course of the 40 reallocations. This is wasting time. If the operating system gets involved with virtual memory paging, you are going to suck up a lot more time.

This overhead can be eliminated by simply .reserve(size_type n)-ing the expected size of the vector ahead of time. With sufficient memory allocated to the vector upfront, no reallocations will occur, and no copies will occur.

    for (unsigned long long i = 7;; i += 2) 
    {
        for (int j = 0; i % primes[j] != 0; ++j)  
        {
            if (sqrt(i) <= primes[j]) 
            {

When i is a prime number or semi-prime number in the order of, say, one million, you are looping over all the prime numbers upto the square root of a million, to see if any of them can divide your current number.

How many different values will sqrt(i) evaluate to over those thousand iterations? Or phrased another way, how many times are you computing the same square root? You may want to move that sqrt(i) calculation out of the inner loop.

    for (unsigned long long i = 7;; i += 2)

If you let this loop run over night, or even over a fort-night, will this loop ever end? No! i will overflow the long long and become negative, and slowing increment back towards positive numbers and repeat. Forever is not long enough. Use i > 0 as the loop test condition.

A long long has at least 64 bits. A double has only a 52 bit mantissa. This means when you pass a large long long to sqrt( ), you will end up losing a few bits, which can make your sqrt() return slightly the wrong value. When you test sqrt(i) <= primes[j], if i is greater than 2^52, and is a perfect square, you might return a value slightly less than the correct value and fail to test the last prime value, and erroneously declare the perfect square a prime number.

You are stuffing long long values into a std:vector<int> container. After a while, they ain't gonna fit.

You are using long long for your prime number candidates, which means you expect to find some prime numbers above 2^31.

The Prime Number Theorem tells us the density of prime numbers in that range to be around 1/21. Or, after testing numbers up to 21 billion, you should have found around 1 billion prime numbers.

Your prime number index j is declared as an int. An int is only guaranteed to have 16 bits. You would need at least a long to guarantee 32 bits. But if you hope to find prime numbers up to 2^52, you have to expect to find 2^45 primes, which even exceeds a long. Your j index should be a long long as well.

Finally, as mentioned in the comments, look at the Sieve of Eratosthenes.