Prime number check

This is a discussion on Prime number check within the C++ Programming forums, part of the General Programming Boards category; I'm making a program that is supposed to get the sum of all prime number in a specified range which ...

  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
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    Hmmm...
    And what will your function return for 9? or 25? true or false?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  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
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    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, 04: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, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21