How does my code addition effect the result?

ArtlessDodger · February 23rd, 2009, 06:33 PM

I'm in Chapter 4, learning about pointers. There is a sample program, Ex4_09.cpp, for calculating and printing out the first 100 prime numbers. This got me curious and instead of printing out the first 100 primes I went for the first 50,000 primes. It took 14 seconds to calculate before printing it out. (I say 14, but that was just me counting seconds.) I then tried the first 1,000,000 but after ten minutes I aborted the progam. I did have to include this line to get it to compile:

Code:

#pragma comment(linker, "/STACK:12345678")

Anyway, I continued reading the book and Ivor mentions that the code would be more efficient if we only divided by primes less than or equal to the square root of the trial number. So I included the cmath library and added a couple of lines:

Code:

    do
    {
        trial += 2; 

        // I added this line:
        long compare = static_cast<long>(sqrt(static_cast<double>(trial)));


        found = 0; // Set found indicator
        for(int i = 0; i < count; i++) // Try division by existing primes
        {
            
            //And I added this line:
                if (*primes+i < compare)


                found = (trial % *(primes + i)) == 0;// True for exact division

                if(found) // If division is exact
                    break; // itâs not a prime
        }

I used static_cast twice so it would compile without warnings. Now this doubled the speed. I counted 7 seconds for 50,000 numbers instead of 14. But it also gave me two less prime numbers. With my added lines the highest prime I got was 611939. But using the code as it is found in the book, I also get 611951 and 611953.

Now the formatting of the numbers is the same. IOW I still have the same number of rows and columns. So, that seems to say that my calculation found two prime numbers less than 611939. Which to me indicates that there is a mistake in my logic. The casting has somehow altered the results.

I'm no mathmetician. Can anyone explain this for me?

Thanks.

ArtlessDodger · February 23rd, 2009, 07:06 PM

After posting this and again looking at my code I realized my condition was specified as "less than" instead of "less than or equal to". So, I changed that and that corrected the results.

But I'm still confused. I had to have 50,000 results, because that's what MAX is equal to. But my faulty results ended with the number 611939. And the correct results ended with the numbers 611939, 611951 and 611953. But since both sets of numbers contained 50,000 members, that means my faulty results had two numbers that the correct results didn't have.

Why would leaving out the = add more numbers instead of leaving some numbers out?