Does anyone have any idea on why the program may crash? The input is prime numbers, and you have to search the next one. If you input a non-prime, it stops. Thanks.
#include <iostream>
using namespace std;
int nextprime (int);
bool primality (int);
int main () {
int a;
cin >> a;
bool prime = primality(a);
while (prime) {
cout << nextprime(a) << endl;
cin >> a;
prime = primality(a);
}
}
int nextprime (int x) {
++x;
if (x % 2 == 0 and x != 2) ++x;
bool prime = primality(x);
while (not prime) {
x = x + 2;
prime = primality (x);
}
return x;
}
bool primality (int x) {
if (x % 2 == 0 and x != 2) return false;
for (int number = 3; number*number <= x; number = number + 2) {
if (x % number == 0) return false;
}
return true;
}
Everything works for me, even big prime numbers. I don't know what makes it fail. It works for everything I input, but the "code judge" still gives execution error
One slight speed improvement.
Change this:
for (int number = 3; number*number <= x; number = number + 2) {
if (x % number == 0) return false;
}
To this:
const int sqrtX = (int)(std::sqrt(x) + 1); // some implementations of sqrt have rounding issues even within the 32-bit range. So +1 isn't a bad idea
for (int number = 3; number <= sqrtX; number = number + 2) {
if (x % number == 0) return false;
}
It trades off multiplying number*number on each iteration to just comparing number against the square root of x, which is only computed once. Make sure to #include <cmath> so you get the sqrt function.
If you don't want to code Sieve of Eratosthenes, you can take advantage of the fact that you can skip not just odd numbers, but multiples of 3 and 5 too. You can reference my faster than average isPrime function on my github: https://github.com/jselbie/isprime/blob/master/isprime.cpp
Basically, in your loop, you're doing a mod check on exactly half the numbers leading up to sqrt(x). You can get that down to 8 mod checks per jump of +30 on number. That will reduce the runtime of your original algorithm down by about half again.
Another hint that may or may not be applicable. If you know all the prime numbers between 2..N (where N is prime). Let's call this set P. Then as you are evaluating the possible candidates for "next prime after N", you only need to do mod tests using the numbers in P.