The next prime number

Question

Among the given input of two numbers, check if the second number is exactly the next prime number of the first number. If so return "YES" else "NO".

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int nextPrime(int x){
   int y =x;
    for(int i=2; i <=sqrt(y); i++){
       if(y%i == 0){
           y = y+2;
           nextPrime(y);
           return (y);
       }
    }
    return y;
}

int main()
{
    int n,m, x(0);
    cin >> n >> m;
    x = n+2;
    if(n = 2 && m == 3){
        cout << "YES\n";
        exit(0);
    }
     nextPrime(x) == m ? cout << "YES\n" : cout << "NO\n";
     return 0;
}

Where is my code running wrong? It only returns true if next number is either +2 or +4. Maybe it has something to do with return statement.

Answer 1

Something to do with the return statement

I would say so

       y = y+2;
       nextPrime(y);
       return (y);

can be replaced with

       return nextPrime(y + 2);

Your version calls nextPrime but fails to do anything with the return value, instead it just returns y.

It would be more usual to code the nextPrime function with another loop, instead of writing a recursive function.

Answer 2

I can tell you two things you are doing wrong:

Enter 2 4 and you will check 4, 6, 8, 10, 12, 14, 16, 18, ... for primality forever.

The other thing is

       y = y+2;
       nextPrime(y);
       return (y);

should just be

       return nextPrime(y + 2);

Beyond that your loop is highly inefficient:

for(int i=2; i <=sqrt(y); i++){

Handle even numbers as special case and then use

for(int i=3; i * i <= y; i += 2){

Using a different primality test would also be faster. For example Miller-Rabin primality test:

#include <iostream>
#include <cstdint>
#include <array>
#include <ranges>
#include <cassert>
#include <bitset>
#include <bit>

// square and multiply algorithm for a^d mod n
uint32_t pow_n(uint32_t a, uint32_t d, uint32_t n) {
    if (d == 0) __builtin_unreachable();
    unsigned shift = std::countl_zero(d) + 1;
    uint32_t t = a;
    int32_t m = d << shift;
    for (unsigned i = 32 - shift; i > 0; --i) {
      t = ((uint64_t)t * t) % n;
      if (m < 0) t = ((uint64_t)t * a) % n;
      m <<= 1;
    }
    return t;
}

bool test(uint32_t n, unsigned s, uint32_t d, uint32_t a) {
    uint32_t x = pow_n(a, d, n);
    //std::cout << "  x = " << x << std::endl;
    if (x == 1 || x == n - 1) return true;
    for (unsigned i = 1; i < s; ++i) {
        x = ((uint64_t)x * x) % n;
        if (x == n - 1) return true;
    }
    return false;
}

bool is_prime(uint32_t n) {
    static const std::array witnesses{2u, 3u, 5u, 7u, 11u};
    static const std::array bounds{
        2'047u, 1'373'653u, 25'326'001u, 3'215'031'751u, UINT_MAX
    };
    static_assert(witnesses.size() == bounds.size());

    if (n == 2) return true; // 2 is prime
    if (n % 2 == 0) return false; // other even numbers are not
    if (n <= witnesses.back()) { // I know the first few primes
        return (std::ranges::find(witnesses, n) != std::end(witnesses));
    }
    // write n = 2^s * d + 1 with d odd
    unsigned s = 0;
    uint32_t d = n - 1;
    while (d % 2 == 0) {
        ++s;
        d /= 2;
    }
    // test widtnesses until the bounds say it's a sure thing
    auto it = bounds.cbegin();
    for (auto a : witnesses) {
        //std::cout << a << " ";
        if (!test(n, s, d, a)) return false;
        if (n < *it++) return true;
    }
    return true;
}

And yes, that is an awful lot of code but it runs very few times.