C++

Forum

 
Nested Prime Number Test For Loops

wolfcry (33)
Hey all,

Been awhile but I was hoping someone could help refresh my memory on something that should be pretty basic in my opinon (and probably is).

I have this code I wrote which tests for primes between a numerical range of 2 - 50.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
#include <iostream>
#include <math.h>
using namespace std;

int prime(int n);

int main() {
    int i;


     for (i = 2; i <= 50; i++) {
                        
         if (prime(i))                       
            cout << i << " is prime" << endl;
         else
            cout << i << " is not prime" << endl;
     }

cout << "Press RETURN to continue...";
cin.get();
return 0;
}


int prime(int n) {
    int i;
    double sqrt_n = sqrt(static_cast<double>(n));

    for (i = 2; i <= sqrt_n; i++) {
        if (n % i == 0)           // If i divides n evenly,
            return false;         //  n is not prime.
    }
    return true;
}


What I was trying to do is basically reverse this and just have two nested For loops without the function. I realize the function is better, but I'm trying to refresh my brain on how to do this and for some reason it's eluding me.


Here's what I have so far:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#include <iostream>
#include <math.h>
using namespace std;

//int prime(int n);

int main()
{

int i;
int is_prime;
int n = sqrt((double) 50);

is_prime = true;
     for (i = 2; i <= 50; i++) {

         for (i = 2; i <= n; i++){
           if(n % i == 0){
              is_prime = false;
              cout << i << "is not prime." << endl;
         } else {
         cout << i << "is prime." << endl;

         }
      }

  }

cout << "Press RETURN to continue...";
cin.get();
return 0;
}


Would someone mind helping me to figure this out? It's driving me nuts lol.
rocketboy9000 (562)
Here's my take on it:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int i;
	for (i = 2; i <= 50; i++) {
		int j;
		double sqrt_i = sqrt((double)i);
		for (j=2;;j++) {
			if(j>sqrt_i){
				cout << i << " is prime" << endl;
				break;
			}else if (i % j == 0){           // If j divides i evenly,
				cout << i << " is not prime" << endl;//it's not prime
				break;
			}
		}
	}
	cout << "Press RETURN to continue...";
	cin.get();
	return 0;
}
wolfcry (33)
hi rocketboy9000,

I was soooo close! lol.

Works like a charm and thank you.

The two parts I was missing was calculating the sqrt of i (which I previously had done but then talked myself out of it thinking it was a bone head move lol) and comparing the nested count to the sqrt_i.

I should have just continued to listen to that annoying little voice in my head.

Again, thanks for the help, I can now sleep in peace lol.
Last edited on
wolfgang (381)
Why not note that you checked all evens so you only need to check by prime numbers?

1
2
3
 
if (i % 2 == 0)
// bad
for (int j = 3; j < sqrt(i); j += 2)
wolfcry (33)
Sorry wolfgang, but I'm not exactly sure what you mean. Where am I dividing "i" by 2?
rocketboy9000 (562)
He means only check for division by 2, not 4,6,8 etc. A little microoptimization.
wolfcry (33)
ah gotcha. Thanks for the help guys!
Topic archived. No new replies allowed.