Prime Numbers C++

[Kourosh23]

The following program checks for prime numbers except 4. 4 is not a prime number, but it says it is prime. Any idea how to fix this bug?

#include <iostream>
using namespace std;

// Program to explain prime numbers.

void functionOne (){
	int n = 0;
	cout << "Enter a number to check if its prime: ";
	cin >> n;

	for (int i = 2; i < n/2; i++){
		if (n % i == 0){
			cout << "\n" << n << " is not a prime number!" << endl;
			exit(0);
		}
	}
	cout<< "\n" << n << " is a prime number." << endl;
}

int main(){
	functionOne();	
	return 0;
}

[integralfx]

for (int i = 2; i < n/2; i++){
When n = 4, the condition would be 2 < 2, which is false. The loop won't run hence, printing "4 is a prime number."

[jonnin]

n/2 is 2.
the loop skips.

the actual logic is probably sqrt(n)+1 ...
not n/2, and go ahead and do i =1?
I forget .. is 1 special or prime? The function should probably work for 1, though.

[Mantorr22]

Line 11 : Note how <= can make a difference instead of <

for (int i = 2; i <= n / 2; i++)

[Kourosh23]

@integralfx, yes that is what I though at first my problem might be.

-------------------------------------
@jonnin

Your idea was interesting, but it wouldn't work unless I considered i = 2 and i <= sqrt(n)+1 for my condition. It works fine for every number except 2. It should be prime, but it says not prime.

Here is the modified code,

#include <iostream>
#include <cmath>
using namespace std;

// Program to explain prime numbers.

void functionOne (){
	int n = 0;
	cout << "Enter a number to check if its prime: ";
	cin >> n;

	for (int i = 2; i <= sqrt(n)+1; i++){
		if (n % i == 0){
			cout << "\n" << n << " is not a prime number!" << endl;
			exit(0);
		}
	}
	cout<< "\n" << n << " is a prime number." << endl;
}

int main(){
	functionOne();	
	return 0;
}

-----------------------------------------------
@Mantor22, smart idea!

It actually works!

#include <iostream>
using namespace std;

// Program to explain prime numbers.

void functionOne (){
	int n = 0;
	cout << "Enter a number to check if its prime: ";
	cin >> n;

	for (int i = 2; i <= n/2; i++){
		if (n % i == 0){
			cout << "\n" << n << " is not a prime number!" << endl;
			exit(0);
		}
	}
	cout<< "\n" << n << " is a prime number." << endl;
}

int main(){
	functionOne();	
	return 0;
}

[Kourosh23]

Just another quick question. What would be the difference if I used break instead of exit(0)?

I actually tried it with break instead of exit(0) and if the number is prime, no problem. However, if it not prime, then it prints out for example

6 is not a prime number!

6 is a prime number.

so, it prints it out two times. I don't understand the logic behind it, any idea why ?

[jonnin]

Its late and I don't see it but I know for sure you only have to test up to just past the square root of a number to find a factor. That is just math... factors come in pairs. Take 9, you have (1,3,3,9). If you find the first 1/2, the second half can be found by division by the first half. So the biggest factor you need to worry about is the square root of N -- and accounting for any round-off errors.

Your loop is doing too much work. Take 100. you only have to find up to 10. Your algorithm looks all the way to 50. This gets worse as n gets bigger, by a lot.

[integralfx]

Just another quick question. What would be the difference if I used break instead of exit(0)?

I actually tried it with break instead of exit(0) and if the number is prime, no problem. However, if it not prime, then it prints out for example

6 is not a prime number!

6 is a prime number.

for (int i = 2; i <= n/2; i++){
    if (n % i == 0){
        cout << "\n" << n << " is not a prime number!" << endl;
        //exit(0);
        break;
    }
}
cout<< "\n" << n << " is a prime number." << endl;

n = 6, i = 2
if (n % i == 0){ is executed as 6 % 2 == 0 is true.

"6 is not a prime number!"

break; causes the for-loop to stop.

"6 is a prime number."

Your idea was interesting, but it wouldn't work unless I considered i = 2 and i <= sqrt(n)+1 for my condition. It works fine for every number except 2. It should be prime, but it says not prime.

n = 2, sqrt(n) + 1 = 1 + 1 = 2
Hence the loop executes.
if (n % i == 0){ is true, outputting

"2 is not a prime number!"

You only need to do up to and including the sqrt(n), so remove the +1. You could also do it like this, without relying on integer truncation and the cmath header. It's functionally equivalent to i <= sqrt(n).
for (int i = 2; i*i <= n; i++){

[mbozzi]

What would be the difference if I used break instead of exit(0)?

Do not use exit(0) in this context.
Except in very rare cases, it will not do what you want; throw an exception instead, if you must.

[Kourosh23]

@jonnin, ok I look further into that, but thanks for your ideas. They were helpful.
-----------------------------------------
@integralfx, I see , so break only exits out of the for loop, while the rest of the program afterward will still run and output. However, exit() function as the name says, exits the whole function. It makes sense.


Also, I modified the code, and it works. I will post both versions at the end, so people can find the solutions all at once easier. Thanks for your help. :)

[Kourosh23]

// Correct version 1:

#include <iostream>
using namespace std;

// Program to explain prime numbers.

void functionOne (){
	int n = 0;
	cout << "Enter a number to check if its prime: ";
	cin >> n;

	for (int i = 2; i <= n/2; i++){
		if (n % i == 0){
			cout << "\n" << n << " is not a prime number!" << endl;
			exit(0);
		}
	}
	cout<< "\n" << n << " is a prime number." << endl;
}

int main(){
	functionOne();	
	return 0;
}

// Correct version 2.
#include <iostream>
using namespace std;

// Program to explain prime numbers.

void functionOne (){
	int n = 0;
	cout << "Enter a number to check if its prime: ";
	cin >> n;

	for (int i = 2; i*i <= n; i++){
		if (n % i == 0){
			cout << "\n" << n << " is not a prime number!" << endl;
			exit(0);
		}
	}
	cout<< "\n" << n << " is a prime number." << endl;
}

int main(){
	functionOne();	
	return 0;
}

// Correct Version 3:

#include <iostream>
#include <cmath>
using namespace std;

// Program to explain prime numbers.

void functionOne (){
	int n = 0;
	cout << "Enter a number to check if its prime: ";
	cin >> n;

	for (int i = 2; i <= sqrt(n); i++){
		if (n % i == 0){
			cout << "\n" << n << " is not a prime number!" << endl;
			exit(0);
		}
	}
	cout<< "\n" << n << " is a prime number." << endl;
}

int main(){
	functionOne();	
	return 0;
}

[lastchance]

1 isn't a prime number ... whatever your 3 functions say.

[Kourosh23]

Hmmm, yes all the codes say that 1 is a prime number.

[TheIdeasMan]

Hi,

Unfortunately your algorithm is the usual naive version of trial division that we see all the time. It may well work for small numbers, but try it for numbers > 1 million and you will see that it gets terribly slow.

Have a look on wiki, there is a Euler's sieve, also Atkins sieve.

One can do Euler's sieve in basically 2 lines of code.

With 1 not being a prime number, check out the "Euclid's fundamental theorem of arithmetic"

[Kourosh23]

@TheIdeasMan, yeah I am a junior c++ programmer, just learned the syntax, and I am doing as many as problems and examples as possible to strengthen my problem solving and logical reasoning.

But at some point, I definitely need to look for more code efficiency. I'll dig deeper into that. Thanks for the info.

[TheIdeasMan]

Actually none of last 3 programs are correct. If you run them it should be obvious why not.

... and I am doing as many as problems and examples as possible to strengthen my problem solving and logical reasoning.

Try to figure out why that algorithm is so slow. Analyse what happens with each new value of i.

When coding, try to work out if the efficiency will be ok, if you have 1 million items in the data set. This will force you to think about what is happening and why.