Prime Adjacent

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
1 upvote
Asked in company
IBM

Problem statement

A prime adjacent is a number that is adjacent to two prime numbers. Two numbers are considered adjacent to each other if the absolute difference between them is 1.

For Example: 
4 is a prime adjacent because it is adjacent to the numbers 3 and 5, which are prime numbers.

Your task is to find out if the number given to you is prime adjacent or not.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case or query contains an integer N.
Output format: 
For each test case, print “Yes” if N is prime adjacent, otherwise print “No” (without inverted commas), in a separate line.
Constraints: 
1 <= T <= 1000
2 <= N <= 10^6

Time limit: 1 sec
Sample Input 1:
2
4 
2
Sample Output 1 :
Yes
No
Explanation :
For test case 1:
4 is a prime adjacent because its adjacent numbers, 3 and 5 are prime numbers.

For test case 2:
In case of 2, the adjacent numbers are 1 and 3, out of which 1 is not prime but 3 is     
prime. 

By definition, a number is a prime adjacent only if both of its adjacent numbers are prime numbers. So, 2 is not a prime adjacent.
Sample Input 2:
3
3 
18
25
Sample Output 2 :
No
Yes
No
Hint

The very first approach can be to check whether the number N-1 and the number N+1 are prime or not. The idea is to use recursion for this task.

Approaches (4)
Recursive Solution

The first thing to observe is that all the odd numbers are non-prime adjacent as their adjacent numbers are always even (which are divisible by 2). So, if the given number is odd, simply return false. Thus, our target is to check only for even numbers.

 

Now the approach is to check recursively for a number if it is prime or not.

 

  • We will call a checker function that checks if the number is prime or not.
  • The algorithm for the checker function will be as follows:
    Here, num is the variable that will store all the possible divisors of the given number ‘N’ except 1 and N itself. The possible divisors are 2 to N - 1, thus, initialize num with 2.
  • bool checker( N, num):
  • If N == num, return true.
  • If N is divisible by num, this confirms that N is not prime, return false.
  • Otherwise: return checker(N , num+1)
Time Complexity

O(N) per test case, where N is the given number.

 

In the worst case, the checker function is called for max N times.

Space Complexity

O(N) per test case.

 

In the worst case, extra space is used by the recursion stack which goes to a maximum depth of N.

Code Solution
(100% EXP penalty)
Prime Adjacent
Full screen
Console