# [C++] IsPrime(int x)

Discussion in 'General Programming Support' started by tooltiperror, Apr 22, 2010.

1. ### tooltiperrorSuper ModeratorStaff Member

Ratings:
+233 / 0 / -0
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.
}
```

2. ### Slapshot136Divide et impera

Ratings:
+483 / 2 / -0
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

3. ### tooltiperrorSuper ModeratorStaff Member

Ratings:
+233 / 0 / -0
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;
cin>>input;
if (input%2!=0 and input%3!=0) {
return 0;
}
return 0;
}
```

4. ### Slapshot136Divide et impera

Ratings:
+483 / 2 / -0
your test there only works for small numbers, it would mark 25 as prime for example

5. ### tooltiperrorSuper ModeratorStaff Member

Ratings:
+233 / 0 / -0
That's because I would have to add in a loop for additional numbers through 9, right?

6. ### XienophYou can change this now in User CP.

Ratings:
+43 / 0 / -0
Why 9? I think you can do better than that

7. ### tooltiperrorSuper ModeratorStaff Member

Ratings:
+233 / 0 / -0
What number can not be divided from a number from 2-9 but it still composite?

8. ### Slapshot136Divide et impera

Ratings:
+483 / 2 / -0
something like 11^2, or actually any prime number greater then 9 squared, or any 2 prime numbers greater then 9 multiplied

9. ### monoVertexI'm back!

Ratings:
+459 / 0 / -0
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.

• Like x 1
10. ### tooltiperrorSuper ModeratorStaff Member

Ratings:
+233 / 0 / -0
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;
cin>>input;
if (isPrime(input)==1) {
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;
}
```

11. ### XienophYou can change this now in User CP.

Ratings:
+43 / 0 / -0
Or better: square root of x.

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

12. ### DarthfettSuper Mod

Ratings:
+613 / 0 / -0
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.

13. ### Dave312Censored for your safe viewing

Ratings:
+269 / 0 / -0
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)

14. ### tooltiperrorSuper ModeratorStaff Member

Ratings:
+233 / 0 / -0
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;
}
```

15. ### XienophYou can change this now in User CP.

Ratings:
+43 / 0 / -0
Don't you want y <= x / 2? Not y == x/2?

16. ### tooltiperrorSuper ModeratorStaff Member

Ratings:
+233 / 0 / -0
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;
cin>>input;
if (isPrime(input)==1) {
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;
}
```

17. ### XienophYou can change this now in User CP.

Ratings:
+43 / 0 / -0
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.

18. ### DarthfettSuper Mod

Ratings:
+613 / 0 / -0
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.

• Like x 1
19. ### XienophYou can change this now in User CP.

Ratings:
+43 / 0 / -0
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)

• Like x 1
20. ### tooltiperrorSuper ModeratorStaff Member

Ratings:
+233 / 0 / -0
I'm a bit confused. How would I find the square root of the number?