Thread: Prime detector

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    5

    Prime detector

    Hello everyone, i'm new to c++. I'm currently trying to make a program that finds the first prime above 1 billion, but i can't make it work. it just prints all numbers from 1 billon to infinity. This is my code:

    Code:
    #include <iostream>
    #include <math.h>
    using namespace std;
    
    int prime(int n);
    
    int main () {
        int i;
        
        for (i = 100000000;; i++) {
            if (prime(i))
               cout << "Dette er er det første primtal over 1 milliard: " << i << endl;   
               break;
        }
        cin.get();
        return 0;               
    
    }
    
    int prime(int n) {
        int i;
        double sqrt_of_n = sqrt(n);
        
        for (i = 2; i <= sqrt_of_n; i++) {
            if (n % i == 0)
            
               return false;
        }
        return true;
    }
    I hope you can help me!

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Hmm ... I'd expect this code to print nothing at all, actually. You're missing braces for the if, and the break is therefore always executed.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    5
    Quote Originally Posted by CornedBee View Post
    Hmm ... I'd expect this code to print nothing at all, actually. You're missing braces for the if, and the break is therefore always executed.
    What should i change to make it work? I started learning the language a couple of days ago, and i'm a bit unsure on the syntax still.

  4. #4
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Code:
    #include <iostream>
    #include <math.h>
    using namespace std;
    
    int prime(int n);
    
    int main () {
        int i;
        
        for (i = 100000000;; i++) {
            if (prime(i))
            {
               cout << "Dette er er det f&#248;rste primtal over 1 milliard: " << i << endl;   
               break;
            }
        }
        cin.get();
        return 0;               
    
    }
    
    int prime(int n) {
        int i;
        double sqrt_of_n = sqrt(n);
        
        for (i = 2; i <= sqrt_of_n; i++) {
            if (n &#37; i == 0)
            
               return false;
        }
        return true;
    }

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Code:
            if (prime(i)) {
               cout << "Dette er er det f&#248;rste primtal over 1 milliard: " << i << endl;   
               break;
    }
    This is the minimum. Though I still don't know why it would print all numbers.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Registered User
    Join Date
    Nov 2008
    Posts
    5
    Quote Originally Posted by CornedBee View Post
    Code:
            if (prime(i)) {
               cout << "Dette er er det første primtal over 1 milliard: " << i << endl;   
               break;
    }
    This is the minimum. Though I still don't know why it would print all numbers.
    I'm sorry the code i posted before wasn't the one that printed all numbers, that was an earlier version of the program. As you said, this program did absolutely nothing. Thanks for the help both of you, i'll see if it works now.

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    It will work.... but like CornedBee said, you may not end up with exactly what you want. That is not how the algorithm you are trying to encorporate even works.... You have merged two ways of determining primality into one half-assed one.

  8. #8
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    >>You have merged two ways of determining primality into one half-assed one.
    Slightly harsh wording don't you think lol?

  9. #9
    Registered User
    Join Date
    Nov 2008
    Posts
    5
    Quote Originally Posted by master5001 View Post
    It will work.... but like CornedBee said, you may not end up with exactly what you want. That is not how the algorithm you are trying to encorporate even works.... You have merged two ways of determining primality into one half-assed one.
    If it won't do what i want it to, why? And what is wrong in how i find a prime? I'd like criticism, if my mistakes aren't corrected i won't get better at c++. Would you please continue to help me by explaining?

  10. #10
    Registered User
    Join Date
    Jun 2008
    Posts
    266
    double sqrt_of_n = sqrt(n);
    I recognize this line of code anywhere. C++ Without Fear!!!

  11. #11
    Registered User
    Join Date
    Nov 2008
    Posts
    5
    Quote Originally Posted by lruc View Post
    double sqrt_of_n = sqrt(n);
    I recognize this line of code anywhere. C++ Without Fear!!!
    You sound like that's the spawn of the devil

    And yes, that's the book i'm learning from.

  12. #12
    Registered User
    Join Date
    Jun 2008
    Posts
    266
    Quote Originally Posted by Elswyyr View Post
    You sound like that's the spawn of the devil

    And yes, that's the book i'm learning from.
    No way. I loved that book! Good choice. Just realize the fact that the book doesn't cover everything so to get information on things like templates and stl, you will need a more advanced book.

  13. #13
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Quote Originally Posted by Raigne View Post
    >>You have merged two ways of determining primality into one half-assed one.
    Slightly harsh wording don't you think lol?
    Harsh, and wrong. That method will work. He is just checking all the numbers below the square root and if there is no remainder after devision the number is obviously composite. If it makes it through every number then it is obviously prime.

    There are far mroe highly optimized methods in use, but for only finding one prime number that one probably executes ina few ms so its fine.

  14. #14
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    If I am not mistaken does this algorithm not also produce pseudo primes as well? *shrugs* I don't care one way or another.

  15. #15
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Nope, no pseudo-primes. Only true primes.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  2. prime number detector program
    By navarrowee in forum C Programming
    Replies: 6
    Last Post: 01-23-2009, 02:45 AM
  3. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  4. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 04:32 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM