Day 10 | Panoramix's Prediction | C++

There are multiple good things about this question.

• It is easy, so you can easily solve it.

• This is a simple question with a lot of distracting background story.

• It is about prime numbers, which are used way too much in competitive programming

• We can learn some techniques which are overkill for this question but very useful for the future.

Let's start with solving this question first. I would ask you to read the question 2-3 times to try to understand what it is asking because we will gradually need a skill to effectively understand how to read problems with a lot of unnecessary background stories.

The problem is ultimately asking if M is the next prime number after N

To solve this, we can find the next prime number after N and check if it is M. We can run an infinite loop through N+1 to infinity and check if a number is prime or not. If it is prime, we will find our next prime number.

How do we check if a number is prime or not

To answer this question, let's ask ourselves what is a prime number. It is a number that is not divisible by any number other than 1 and itself. So, we can simply follow the definition and check if it actually is divisible by any number between 2 to X-1 [X = Number we are checking for prime]

Like this,

bool is_prime(int X){
	for(int i = 2; i < X; i++){
		if(X % i == 0) { 
			/**
			  * If X is divisble by i, we will return false
			  * As that states, it is not prime and
			  * our function - is_prime(X) -> false 
			***/
			return false;
		}		
	}
	return true; //Default case, if we could'nt find any number x 
			    //divisible by.
}

We can similarly write the complete solution like this - Link to Codeforces Submission

#include<iostream>
using namespace std;

bool is_prime(int x){
    for(int i = 2; i < x; i++){
        if(x % i == 0)return false;
    }
    return true;
}

int main(){
    int n, m;
    cin >> n >> m;
    // Finding next prime number
    int next = n+1;
    while(true){
        if(is_prime(next))break;
        next++;
    }
    if(next == m){
        cout << "YES";
    }else{
        cout << "NO";
    }
    return 0;
}

Time to over-optimize this solution

Here, we were checking primes up to N = 50 only (read constraints in the question). But we might also need to do so for big numbers in the future. So let's bring some technique which is very common.

Sqrt Prime Check Do this activity, take any number of your choice (say X) and write down its factors. Let's say A and B are two factors. and, A > sqrt(X) and also B > sqrt(X) then A x B > X This is not possible as we know A x B = X thus, we can say if A > sqrt(X), then B < sqrt(X) So if we are unable to find any factor of X till sqrt(X), we won't find it after sqrt(X) as well. So, we can change complexity of is_prime(int X) from O(X) to O(sqrt(X)).

bool is_prime(int X){
	for(int i = 2; i*i <= X; i++){
		if(X % i == 0) { 
			return false;
		}		
	}
	return true; 
}