[C++] IsPrime(int x)

[tooltiperror]

I've been writing a function in C++ to see if something is prime. My first thought process was that you could check to see if something is composite by seeing if it was divisible by a number in a loop, and exit when the integer reaches the integer x, the argument. The problem is, I can't find out how to check if something is a whole number.


This is what I have so far (I am aware it's incomplete):

{
	int y;
	for (y=1; NULL; y++) {
		if (x=1) {
			//It is composite,
			return 1; // so return 1.
		}
	} // If it isn't composite, it
	return 0; // must be prime.
}

 

[Slapshot136]

look into the mod operator (%) - it returns the "remainder" - if the remainder is 0, then it divides nicely

also, you only need to check up the the square root of the number, because lets say the number you are checking is 14 - you will notice that "2" and "7" both divide into it, but they are a pair (one above the square-root mark, and one below the square-root mark, or both are the exact square root if it's a perfect square) - you can stop once you find 2, and if you don't find any up to the square-root mark, then you know that there won't be any after that

 

[tooltiperror]

Oh, thanks, I think I know what to do now.

Edit: Figured it out.

 int main ()
{
	int input;
	int x;
	int y;
	int cc;
	cout<<"Please enter a number: ";
	cin>>input;
	if (input%2!=0 and input%3!=0) {
		cout<<"Your number is prime.\n";
		return 0;
	}
	cout<<"Your number is composite.\n";
	return 0;
}

 

[Slapshot136]

your test there only works for small numbers, it would mark 25 as prime for example

 

[tooltiperror]

your test there only works for small numbers, it would mark 25 as prime for example

That's because I would have to add in a loop for additional numbers through 9, right?

 

[Xienoph]

That's because I would have to add in a loop for additional numbers through 9, right?

Why 9? I think you can do better than that

 

[tooltiperror]

What number can not be divided from a number from 2-9 but it still composite?

 

[Slapshot136]

What number can not be divided from a number from 2-9 but it still composite?

something like 11^2, or actually any prime number greater then 9 squared, or any 2 prime numbers greater then 9 multiplied

 

[monoVertex]

Ideally, you are supposed to loop till x/2, to be sure . Like slapshot said, 121 is a number that is not divided by 2-9, but it still composites.

 

[tooltiperror]

Ideally, you are supposed to loop till x/2, to be sure . Like slapshot said, 121 is a number that is not divided by 2-9, but it still composites.

The x/2 thing totally just gave me a huge idea.

Will edit this post with a (I think) correct code.

Edit:

Now, for some reason, what I thought was correct, skips 5 as a prime number.

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

int isPrime(int x);

 int main ()
{
	int input;
	int count;
	int y;
	cout<<"Please, enter a number: ";
	cin>>input;
	if (isPrime(input)==1) {
		cout<<"Your number is already prime.\n";
		return 0;
	}
	for (count=input; y!=1; count++) {
		if (isPrime(count)==1) {
			cout<<"The next prime number is "<<count<<".\n";
			y=1;
		}
	}
	cin.get();
	return 0;
}

  int isPrime(int x)
{
	//int z=x%2;
	//int y=x%3;
	//int w=x%5;
	//if (z!=0 && y!=0 or x==3) {
	//	return 1; //1=prime;
	//}
	
	int y;
	for (y=1; y < x/2; y++) {
		if (x%y!=0) {
			return 1;
		}
	}
	return 0;
}

 

[Xienoph]

Ideally, you are supposed to loop till x/2, to be sure . Like slapshot said, 121 is a number that is not divided by 2-9, but it still composites.

Or better: square root of x.

A further optimization would be to start with Miller Rabin Primality Test

 

[Darthfett]

I would start the loop with 2, since all numbers are divisible by 1.

I've never heard of, or seen that Miller-Rabin test, but it is quite confusing.

 

[Dave312]

You really only need to try and divide by prime numbers as well. However writing code to do that would be rather tricky. So instead you should check if the number is even (if it is then it is definitely not a prime unless the number is 2), then start looping from 3 and use a step of 2 so that you are only checking odd numbers. This would half the time it takes (useful for large numbers)

 

[tooltiperror]

Alright, now I'm really confused.

My thought process was that if you can be divided evenly by anything greater than one and less than half of you, you're composite. But the problem is, my loop isn't working correctly, and I'm not sure why.

  int isPrime(int x)//1==prime;
{	
	int y;
	for (y=2; y==x/2; y++){
		if (x%y==0) {
			return 0;
		}
	}
	return 1;
}

 

[Xienoph]

Don't you want y <= x / 2? Not y == x/2?

 

[tooltiperror]

Works now, thanks. Will it work now forever?

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

int isPrime(int x);

 int main ()
{
	int input;
	int count;
	int y;
	cout<<"Please, enter a number: ";
	cin>>input;
	if (isPrime(input)==1) {
		cout<<"Your number is already prime.\n";
		return 0;
	}
	for (count=input; y!=1; count++) {
		if (isPrime(count)==1) {
			cout<<"The next prime number is "<<count<<".\n";
			y=1;
		}
	}
	cin.get();
	return 0;
}

  int isPrime(int x)
{	
	int y;
	for (y=2; y<=x/2; y++)
	{
		if (x%y==0) 
		{
			return 0;
		}
	}
	return 1;
}

 

[Xienoph]

I think it looks good. As I have said, an optimization would be to stop at square root of x. Why? Well, suppose a number n is a composite. Then n = a * b. But one of a or b must be less than square root of n (think about it for a second ... use calculus if you're still not convinced). So, it is sufficient to check everything from 1 to square root of n.

 

[Darthfett]

So, it is sufficient to check everything from 1 to square root of n.

n = a * b. If a is 1, b is automatically going to be equal to n. Use 2, as it is the next integer in the sequence 1 to n.

 

[Xienoph]

n = a * b. If a is 1, b is automatically going to be equal to n. Use 2, as it is the next integer in the sequence 1 to n.

Yes, that's true. A further optimization, as suggested by Dave, would be to check for only odd numbers (after checking that n is not 2, of course)

 

[tooltiperror]

I'm a bit confused. How would I find the square root of the number?