Prime Adjacent

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)

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 idea is to check separately if the number N - 1 and the number N + 1 are prime or not.  

The approach is to check iteratively for a number if it is prime or not. 

• For the number N - 1:
  Run a loop from 2 to N - 2 to look for its divisibility, if it is divisible by any number, it confirms that it is not prime.
• Similarly,  for the number N - 2:
  Run a loop from 2 to N-1 to look for its divisibility, if it is divisible by any number, it confirms that it is not prime.
• If both N-1 and N-2 are prime numbers, means our number N is prime adjacent, thus, return true.
  Return false, otherwise.

Note :

Rather than checking till N-1 for a number N, we can check till N/2. As any divisor of a number will not be greater than half of that number. But, this is a very minute improvement, the time complexity still remains the same.

Let us see how we can find out if a number X is prime or not.

• The idea is to take the range as root(X).
• Let X = a * b.
  As, any non prime number X can be represented as root(X)*root(X) =  X.
  So, if one factor of X is greater than root(X), the other is definitely less than root(X).
  For example: consider X = 36.
  → So, root(36) =  6. Now, if one factor of 36 is greater than 6, say 12, then the other factor is 36/12 = 3, which is less than 6. 
  → Similarly, if we take one factor as 18, then the other factor is 36/18 = 2, which is also less than 6.
• So, in the case of the number N-1, rather than looking for all the numbers from 2 to N-1, we will look for 2 to root(N-1) to look for any divisor of N-1.
• Similarly, for the number N+1, we will look for all numbers from 2 to root(N+1). 

The logic remains the same, we will check if the adjacent numbers are prime or not. For that we will use the below algorithm:
The approach is to precompute all prime numbers using the Sieve of Eratosthenes.

• The idea is to take a check array of size N (up to which we want to find the primes) and mark all numbers as prime initially.
• Then, iteratively mark the multiples of each prime as composite (that is, not prime).
• We start with the first prime number i.e. 2.
• For example, Suppose we want to find all prime numbers smaller than N i.e. 20.
  → Firstly, we will create a boolean array of size 20 and mark all the indices as prime, say true.
  →Then, we will start from the very first prime number 2, it is now obvious that all the multiples of 2 will be non - prime. Thus, we mark all multiples of 2 i.e. 4, 6, 8, and so on till 20 as non-prime.
  → Now, our next prime is 3 as it is not marked composite yet, so, in this iteration, we will mark all multiples of 3 i.e. 6, 9, 12, 15, and so on as non-prime.
• In short, for a prime p, we will mark 2p, 3p, 4p as non-prime.
• These iterations will go on till N/2 as after N/2, the multiples of further numbers won’t be in the range of N.

Algorithm:

 

• For i  less than N/2:
  → If check[i] is true, for all multiples of i which are less than N, assign check[ j ] = false, where j is 2 * i, 3 * i, and so on.

Modifications:

• Now, if we look carefully and as explained earlier, there is no need to iterate through multiples of all prime numbers, we can perform iteration for only those prime numbers which are smaller than a particular number i.e root(N).
• As each number can be expressed as the product of two numbers. So, if any prime number greater than root(N) say b has a multiple smaller than N say, a then a/b is definitely smaller than root(N) as explained in the previous approach. Now, if a/b is prime then a is definitely a multiple of a/b, which means a is already marked by a/b.

Let us take an example, 21 can be represented as 7 * 3.

→ Now, 21 is one of the multiples of 7, So we tried to mark it during the iteration when we take 7 as our prime number. But, if we look carefully,   21 is also the multiple of 3. This means that 21 was already marked earlier by 3 as non-prime.
→ In short, following the above algorithm, when I = 2, we marked 2 * 2, 2 * 3, 2 * 4, and so on as composite. 

→ Now, when I = 3, we will mark 3 * 2, 3 * 3, 3 * 4, and so on as composite. You will see that 3 * 2 is repeated. 

→ Now, when I = 5, we will mark 5 * 2, 5 * 3, 5 * 4, and so on as composite. You will see that 5 * 2 are 5 * 3 are repeated again and in the case of 5 * 4, we are iterating it unnecessarily as it must have been taken care of by 2 during 10 as multiple.  
 

• So, we made 2 things clear,

1. For the first loop in the above algorithm: Rather than iterating for all prime numbers, we will iterate for only those prime numbers which are smaller than root(N).
2. For the second loop in the above algorithm: Rather than starting from 2 * p for a prime number p, we will start from p ^ 2 and then move to p ^ 2 + p, p ^ 2+2 * p, and so on.

Modified Algorithm :

→ For i  less then root(N):
→ If check[i] is true, for all multiples of i which are less than N, assign check[ j ] = false, where j is (i * i), (i * i + i), (i * i + 2 * i) and so on.