Thread: Prime number check

  1. #1
    Registered User
    Join Date
    Apr 2007
    Location
    Sweden
    Posts
    12

    Prime number check

    I'm making a program that is supposed to get the sum of all prime number in a specified range which is in this case 1 000 000. The program works fine, except that it seems to count some prime numbers even if they aren't prime.

    Here is my code:
    Code:
    #include <iostream>
    #include <cmath>
    
    using namespace std;
    
    const int RANGE = 1000000;
    
    bool isPrime(int n) {
        if (n <= 0 || n == 1 || (n % 2 == 0 && n != 2)) 
            return false;
        
        for (int i=3;i<sqrt(n);i++) {
            if ((n%i) == 0) 
                return false;
        }
        return true;
    }
    
    int main(void) {
        unsigned long sumPrimes = 0;
        long counter = 0;
        
        for (int i=0;i<RANGE-1;i++) {
            if (isPrime(i)) {
                cout << i << endl;
                sumPrimes+=i;
                counter++;
            }
        }
        
        cout << "Counter: " << counter << endl;
        cout << "Sum of primes: " << sumPrimes;
    
        while (cin) cin.get();
        return 0;
    }
    I'm fairly certain that the isPrime() function is wrong, since the actual prime count should be somewhere closer to 78000. My program counts exactly: 78665 when the range is 1 000 000. It works fine when I take a lower range. Any ideas/improvements?

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Hmmm...
    And what will your function return for 9? or 25? true or false?
    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
    Apr 2007
    Location
    Sweden
    Posts
    12
    True for both.. so why does it return true for them? I searched around for hours and found out that it's even enough to check if it's divisible with any number until the square root of the checked number. In other words the following code was considered enough:

    bool isPrime(int n) {
    for (int i=3;i<sqrt(n);i++) {
    if ((n&#37;i) == 0)
    return false;
    }
    return true;
    }

    edit: It was because it was supposed to be sqrt(n)+1 instead of sqrt(n). It doesn't return true on number 9 and 25 now, but the main problem still remains.
    Last edited by password; 06-25-2007 at 07:19 AM. Reason: I found out why..

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by password View Post
    True for both.. so why does it return true for them?
    Because you should be looping while "<= sqrt(n)" not just "< sqrt(n)". If the number is square, then sqrt(n) is a factor, but you never check it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. xor linked list
    By adramalech in forum C Programming
    Replies: 23
    Last Post: 10-14-2008, 10:13 AM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Replies: 6
    Last Post: 11-04-2002, 05:11 PM
  4. prime # query
    By alokin in forum C Programming
    Replies: 8
    Last Post: 09-04-2002, 11:50 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM