|
Given three numbers and check whether they are adjacent primes are not. Three prime numbers are said to be adjacent primes if there is no prime between them.
Examples :
Input : 2, 3, 5
Output : Yes
Explanation: 2, 3, 5 are adjacent primes.
Input : 11, 13, 19
Output : No
Explanation: 11, 13, 19 are not adjacent primes.
Because there exists 17 between 13 and 19 which is prime.
Approach:
We already know what is a prime number. Here we need to check whether the given three numbers are adjacent primes or not. First we check given three numbers are prime or not. After that we will find next prime of first number and second number. If satisfies the condition of adjacent primes then it is clear that given three numbers are adjacent primes otherwise not.
C++
<?php
function isPrime($n)
{
if ($n % 2 == 0)
return false;
for ($i = 3; $i * $i <= $n; $i += 2)
if ($n % $i == 0)
return false;
return true;
}
function nextPrime($start)
{
$next = $start + 1;
while (!isPrime($next))
$next++;
return $next;
}
function areAdjacentPrimes($a, $b, $c)
{
if (!isPrime($a) || !isPrime($b) ||
!isPrime($c))
return false;
$next = nextPrime($a);
if ($next != $b)
return false;
if (nextPrime($b) != $c)
return false;
return true;
}
if (areAdjacentPrimes(11, 13, 19))
echo "Yes";
else
echo "No";
?>
|
Time complexity: O(sqrt(n))
Auxiliary space: O(1)
Approach 2: Sieve of Eratosthenes
Another approach to check if three given numbers are adjacent primes or not is to generate all prime numbers up to a certain limit (such as using the Sieve of Eratosthenes) and then check if the given numbers are adjacent primes or not by comparing them with the list of prime numbers.
Here’s the code of above implementation:
C++
#include <bits/stdc++.h>
using namespace std;
vector<int> generatePrimes(int n)
{
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (prime[i]) {
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
vector<int> primes;
for (int i = 2; i <= n; i++) {
if (prime[i]) {
primes.push_back(i);
}
}
return primes;
}
bool areAdjacentPrimes(int a, int b, int c)
{
int maxNum = max(max(a, b), c);
vector<int> primes = generatePrimes(maxNum);
int indexA = find(primes.begin(), primes.end(), a)
- primes.begin();
int indexB = find(primes.begin(), primes.end(), b)
- primes.begin();
int indexC = find(primes.begin(), primes.end(), c)
- primes.begin();
if (indexA + 1 == indexB && indexB + 1 == indexC) {
return true;
}
else {
return false;
}
}
int main()
{
if (areAdjacentPrimes(11, 13, 19)) {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.List;
public class GFG {
private static List<Integer> generatePrimes(int n) {
boolean[] prime = new boolean[n + 1];
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (prime[i]) {
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (prime[i]) {
primes.add(i);
}
}
return primes;
}
private static boolean areAdjacentPrimes(int a, int b, int c) {
int maxNum = Math.max(Math.max(a, b), c);
List<Integer> primes = generatePrimes(maxNum);
int indexA = primes.indexOf(a);
int indexB = primes.indexOf(b);
int indexC = primes.indexOf(c);
if (indexA + 1 == indexB && indexB + 1 == indexC) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
if (areAdjacentPrimes(11, 13, 19)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
|
Python3
def generate_primes(n):
prime = [True] * (n + 1)
prime[0] = prime[1] = False
i = 2
while i * i <= n:
if prime[i]:
for j in range(i * i, n + 1, i):
prime[j] = False
i += 1
primes = [i for i in range(2, n + 1) if prime[i]]
return primes
def are_adjacent_primes(a, b, c):
max_num = max(a, b, c)
primes = generate_primes(max_num)
index_a = primes.index(a)
index_b = primes.index(b)
index_c = primes.index(c)
if index_a + 1 == index_b and index_b + 1 == index_c:
return True
else:
return False
if __name__ == "__main__":
if are_adjacent_primes(11, 13, 19):
print("Yes")
else:
print("No")
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
static List<int> GeneratePrimes(int n)
{
bool[] prime = new bool[n + 1];
for (int i = 0; i <= n; i++)
prime[i] = true;
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (prime[i]) {
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
List<int> primes = new List<int>();
for (int i = 2; i <= n; i++) {
if (prime[i]) {
primes.Add(i);
}
}
return primes;
}
static bool AreAdjacentPrimes(int a, int b, int c)
{
int maxNum = Math.Max(Math.Max(a, b), c);
List<int> primes = GeneratePrimes(maxNum);
int indexA = primes.IndexOf(a);
int indexB = primes.IndexOf(b);
int indexC = primes.IndexOf(c);
if (indexA + 1 == indexB && indexB + 1 == indexC) {
return true;
}
else {
return false;
}
}
static void Main(string[] args)
{
if (AreAdjacentPrimes(11, 13, 19)) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
}
}
|
Javascript
function generatePrimes(n) {
const prime = new Array(n + 1).fill(true);
prime[0] = prime[1] = false;
for (let i = 2; i * i <= n; i++) {
if (prime[i]) {
for (let j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
const primes = [];
for (let i = 2; i <= n; i++) {
if (prime[i]) {
primes.push(i);
}
}
return primes;
}
function areAdjacentPrimes(a, b, c) {
const maxNum = Math.max(a, b, c);
const primes = generatePrimes(maxNum);
const indexA = primes.indexOf(a);
const indexB = primes.indexOf(b);
const indexC = primes.indexOf(c);
if (indexA + 1 === indexB && indexB + 1 === indexC) {
return true;
} else {
return false;
}
}
if (areAdjacentPrimes(11, 13, 19)) {
console.log("Yes");
} else {
console.log("No");
}
|
Time complexity: O(Logn)
Auxiliary space: O(1)
|
