Should Work?

[Opi8]

tl;dr - Check the comments in code for info, tested it for sum of primes below 10 and it works, but it does not give the correct answer when I check for sum of primes below 2 million it does not.

I am not exactly sure why my solution to a problem on Project Euler is not working (I know, it's a lazy way of solving it but at the moment I only have a small amount of coding experience and no computing science experience, so I couldn't figure out an algorithm for this cause I know little about primes other than that they can only be divided by 1 and itself)
The program is meant to find the sum of all primes below 2 million, so I use 2 while loops, the first one is used to count up to 2 million, the second one is used to check if the current number below 2 million is prime or not, by checking if every number from 2 till that number returns a non-zero value when modded (I think that's a good enough explanation, if not than just let me know and I'll clear things up if need be)
Anyways, I tested it for say the sum of all primes below ten, and it works, so I figured maybe the total sum was too large or something, but using a long long int on the p_sum variable made no difference.

//Finds the sum of all primes below 2 million
#include <stdio.h>
int main(void)
{
    int c = 3, c_count, p = 0, p_sum = 2; //"c" counts up to 2 million, "c_count" is a counter used to check if any numbers from 2 to c-1 are prime, "p" is the sum of primes
    while (c < 2000000)//While not 2000000
    {
        c_count = 2; //Resets the counter to 2
        while(c_count <= c)// while the counter <= value being checked
        {
            if (c % c_count != 0)//If value being checked % counter is not 0
            {
                c_count++;// counter++, to check if c % any of the counters will equal 0, if none of them do than it is prime
            }
            else if(c_count == c) // If the numbers are equal, then all counters have been checked, and the number is prime
            {
                p = c; // This p variable is rather unnecessary, it just holds the value of prime (the current value of c, if c_count and c are equal) to be added to the sum of all primes.
                p_sum += p; // Adds the prime to the total sum of all primes under 2 million
                printf("%d\n", p); //Just here to make sure there is no infinite loop
                c++; // So that the next number can be checked to see if it is prime
                c_count += c; // Ends the loop (which will be restarted to check the next value of c once c_count is reset to 2)
            }
            else // Not prime, increments c so the next value can be checked
            {
                c++;
                c_count += c; // end loop
            }
        }
    }
    printf("Sum of all the primes under 2 million is : %d\n", p_sum); //Outputs result
    return 0;
}

Thanks for any help, and for putting up with the noob questions I've started asking lately ^_^

[stahta01]

else // Not prime, increments c so the next value can be checked
            {
                c++;
                c_count += c; // end loop
            }

should be

else // Not prime, increments c so the next value can be checked
            {
                c++;
                c_count = 2; // restart loop counter
            }

Would be clearer as and may give slightly different answers; I think the answer would match the option right above.

else // Not prime, increments c so the next value can be checked
            {
                c++;
                break; // end inner loop
            }

[smokeyangel]

Aye -- use break; to exit the inner loop.

I can't see anything wrong with how you're working out the primes.


I think the problem is:
The sum of all primes below 2 million is > 32 bits so it does have to go in a long long. I know you tried that, but did you also update the printf that prints p_sum to expect a long long? Otherwise the answer might be write but it will print out wrong...

The format specifier for long long is %lld.


The other problem is with performance -- you'll get the correct answer eventually but it's a long wait and not very efficient. A couple of pointers:

- There are no even primes apart from 2. Obviously... because then they'd divide by 2 and wouldn't be primes So, you should increment c_count by 2, not 1.
- Less obvious - you only need to test divisors from 2 to the square root of c. To calculate the square root, #include math.h and call sqrt(c). Program should complete in a few seconds if you do that.

[Opi8]

Aye -- use break; to exit the inner loop.

I can't see anything wrong with how you're working out the primes.


I think the problem is:
The sum of all primes below 2 million is > 32 bits so it does have to go in a long long. I know you tried that, but did you also update the printf that prints p_sum to expect a long long? Otherwise the answer might be write but it will print out wrong...

The format specifier for long long is %lld.


The other problem is with performance -- you'll get the correct answer eventually but it's a long wait and not very efficient. A couple of pointers:

- There are no even primes apart from 2. Obviously... because then they'd divide by 2 and wouldn't be primes So, you should increment c_count by 2, not 1.
- Less obvious - you only need to test divisors from 2 to the square root of c. To calculate the square root, #include math.h and call sqrt(c). Program should complete in a few seconds if you do that.

Ahh, yes I did not realize that I would have to change the conversion specifier, also I had a vague knowledge of the whole square root thing, but most of what I learned from my high school course last year I have forgotten, so I figured I'd just do it a way that I knew would EVENTUALLY work. But you are right, the program takes a long time to (not sure what the term is for when it actually finishes and gives your result, just "complete"?)...anyways I'll first try fixing the long long int, and then later on once I've watched some computing science lectures and such I'll come back to the problem and try a different approach.
And thank you for break, I hadn't learned about it yet, can it be used in any type of loop?