# Prime detector

• 11-05-2008
Elswyyr
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!
• 11-05-2008
CornedBee
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.
• 11-05-2008
Elswyyr
Quote:

Originally Posted by CornedBee
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.
• 11-05-2008
master5001
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; }```
• 11-05-2008
CornedBee
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.
• 11-05-2008
Elswyyr
Quote:

Originally Posted by CornedBee
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.
• 11-05-2008
master5001
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.
• 11-05-2008
Raigne
>>You have merged two ways of determining primality into one half-assed one.
Slightly harsh wording don't you think lol?
• 11-05-2008
Elswyyr
Quote:

Originally Posted by master5001
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?
• 11-05-2008
lruc
double sqrt_of_n = sqrt(n);
I recognize this line of code anywhere. C++ Without Fear!!!
• 11-05-2008
Elswyyr
Quote:

Originally Posted by lruc
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.
• 11-05-2008
lruc
Quote:

Originally Posted by Elswyyr
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.
• 11-05-2008
abachler
Quote:

Originally Posted by Raigne
>>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.
• 11-05-2008
master5001
If I am not mistaken does this algorithm not also produce pseudo primes as well? *shrugs* I don't care one way or another.
• 11-05-2008
CornedBee
Nope, no pseudo-primes. Only true primes.