Thread: Fresh Eyes, Please

  1. #1
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229

    Fresh Eyes, Please

    This is actually for Project Euler (Probably shouldn't be asking for help, but I want to know). I'm trying to find the sum of all prime numbers less then 1,000,000. So, I was just trying to brute force it. I've read over the code a million times, but I can't figure out whats going on.

    It's returning a crazy negative number. -1104303641 to be specific.

    Code:
    #include <iostream>
    #include <vector>
    using namespace std;
    
    bool check_prime(int &num);
    
    int main()
    {
        int total = 2;    //Start at 2, because the loop starts with 3, so still needs to be accounted for.
        for (int c = 3; c < 1000000; c += 2)    //Increment by 2, because primes are odd.
        {
            if (check_prime(c))
            {
                total += c;
            }
            if (c &#37; 729 == 0)        //Get a % completion.
            {
                system("clear");
                cout << (c / 1000000.0f) * 100.0f << "%" << endl;
            }
        }
        cout << "done" << endl;
        cout << "Total: " << total << endl;
        return 0;
    }
    
    /*
    Checks if the number given is prime...I hope.
    */
    bool check_prime(int &num)
    {
        for (int k = 2; k < num; ++k)
        {
            if (num % k == 0)
            {
                return false;
            }
        }
        return true;
    }
    It's very slow too. If you want to compile it you can change 'system("clear")' to what ever you like, or just take it out altogether. So, my main question is, "Why is the total coming out negative?"

    Thanks
    Last edited by IdioticCreation; 07-29-2007 at 10:48 PM.

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    probably - you have overflow
    change total to double to check it...

    And about more optimal prime number search algorithm - search the forum, it was discussed several times
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    I'm guessing that your sum is exceeding the maximum value of an int (consider that the number of primes less than a given number N is roughly N/ln(N), by the Prime Number Theorem, and you could make a ballpark guess as to what the sum should be). BTW, using Eratosthenes' sieve would compute the primes much faster. There was a thread on this a while back.

    http://mathworld.wolfram.com/PrimeNumberTheorem.html

    Edit: http://cboard.cprogramming.com/showthread.php?t=91461
    Last edited by robatino; 07-29-2007 at 11:00 PM.

  4. #4
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    Oh, thanks for the link. I'll try double and let you know how it works.

  5. #5
    Registered User IdioticCreation's Avatar
    Join Date
    Nov 2006
    Location
    Lurking about
    Posts
    229
    Alright, well that fixed the problem. Still not getting the right answer. I got 37,550,400,000 o_0
    So I'm going to redo it I think.

    Thanks for you help,
    David

  6. #6
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    If you want to use system("clear") you must have #include <stdlib.h>.
    Last edited by Differ; 07-30-2007 at 12:13 AM. Reason: Scratch the first part.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. North Carolina's (not so) fresh produce
    By Sebastiani in forum General Discussions
    Replies: 4
    Last Post: 07-01-2009, 11:43 PM
  2. application wont launch on fresh Xp
    By jonezy in forum C++ Programming
    Replies: 10
    Last Post: 01-23-2007, 07:01 AM
  3. Do your eyes bleed?
    By B0bDole in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 11-25-2004, 02:12 AM
  4. Prelude all Eyes on you
    By NewbieVB in forum C++ Programming
    Replies: 2
    Last Post: 04-13-2002, 03:15 AM