[C++] IsPrime(int x)

tooltiperror

Super Moderator
Reaction score
231
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):
Code:
{
	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

Divide et impera
Reaction score
471
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

Super Moderator
Reaction score
231
Oh, thanks, I think I know what to do now.

Edit: Figured it out.

Code:
 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;
}
 

tooltiperror

Super Moderator
Reaction score
231
What number can not be divided from a number from 2-9 but it still composite?
 

monoVertex

I'm back!
Reaction score
460
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

Super Moderator
Reaction score
231
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.

Code:
 #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;
}
 

Dave312

Censored for your safe viewing
Reaction score
269
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

Super Moderator
Reaction score
231
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.

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

tooltiperror

Super Moderator
Reaction score
231
Works now, thanks. Will it work now forever?

Code:
 #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

You can change this now in User CP.
Reaction score
43
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.
 

Xienoph

You can change this now in User CP.
Reaction score
43
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

Super Moderator
Reaction score
231
I'm a bit confused. How would I find the square root of the number?
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top