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++
// CPP program to check given three numbers are// primes are not.#include <bits/stdc++.h>using namespace std;// checks whether given number is prime or not.bool isPrime(int n){ // check if n is a multiple of 2 if (n % 2 == 0) return false; // if not, then just check the odds for (int i = 3; i * i <= n; i += 2) if (n % i == 0) return false; return true;}// return next prime numberint nextPrime(int start){ // start with next number. int next = start + 1; // breaks after finding next prime number while (!isPrime(next)) next++; return next;}// check given three numbers are adjacent primes are not.bool areAdjacentPrimes(int a, int b, int c){ // check given three numbers are primes are not. if (!isPrime(a) || !isPrime(b) || !isPrime(c)) return false; // find next prime of a int next = nextPrime(a); // If next is not same as 'a' if (next != b) return false; // If next is not same as 'c' if (nextPrime(b) != c) return false; return true;}// Driver code for above functionsint main(){ if (areAdjacentPrimes(11, 13, 19)) cout << "Yes"; else cout << "No"; return 0;} |
C
// C program to check given three numbers are// primes are not.#include <stdbool.h>#include <stdio.h>// checks whether given number is prime or not.bool isPrime(int n){ // check if n is a multiple of 2 if (n % 2 == 0) return false; // if not, then just check the odds for (int i = 3; i * i <= n; i += 2) if (n % i == 0) return false; return true;}// return next prime numberint nextPrime(int start){ // start with next number. int next = start + 1; // breaks after finding next prime number while (!isPrime(next)) next++; return next;}// check given three numbers are adjacent primes are not.bool areAdjacentPrimes(int a, int b, int c){ // check given three numbers are primes are not. if (!isPrime(a) || !isPrime(b) || !isPrime(c)) return false; // find next prime of a int next = nextPrime(a); // If next is not same as 'a' if (next != b) return false; // If next is not same as 'c' if (nextPrime(b) != c) return false; return true;}// Driver code for above functionsint main(){ if (areAdjacentPrimes(11, 13, 19)) printf("Yes"); else printf("No"); return 0;}// This code is contributed by kothavvsaakash. |
Java
// Java program to check given three numbers are// primes are not.import java.io.*;import java.util.*;class GFG { public static boolean isPrime(int n) { // check if n is a multiple of 2 if (n % 2 == 0) return false; // if not, then just check the odds for (int i = 3; i * i <= n; i += 2) if (n % i == 0) return false; return true; } // return next prime number public static int nextPrime(int start) { // start with next number. int next = start + 1; // breaks after finding next prime number while (!isPrime(next)) next++; return next; } // check given three numbers are adjacent primes are // not. public static boolean areAdjacentPrimes(int a, int b, int c) { // check given three numbers are primes are not. if (!isPrime(a) || !isPrime(b) || !isPrime(c)) return false; // find next prime of a int next = nextPrime(a); // If next is not same as 'a' if (next != b) return false; // If next is not same as 'c' if (nextPrime(b) != c) return false; return true; } // Driver code for above functions public static void main(String[] args) { if (areAdjacentPrimes(11, 13, 19)) System.out.print("Yes"); else System.out.print("No"); }}// Mohit Gupta_OMG <(o_0)> |
Python
# Python3 program to check given# three numbers are primes are not.# Function checks whether given number is prime or not.def isPrime(n): # Check if n is a multiple of 2 if (n % 2 == 0): return False # If not, then just check the odds i = 3 while(i*i <= n): if (n % i == 0): return False i = i + 2 return True# Return next prime numberdef nextPrime(start): # Start with next number nxt = start + 1 # Breaks after finding next prime number while (isPrime(nxt) == False): nxt = nxt + 1 return nxt# Check given three numbers# are adjacent primes are notdef areAdjacentPrimes(a, b, c): # Check given three numbers are primes are not if (isPrime(a) == False or isPrime(b) == False or isPrime(c) == False): return False # Find next prime of a nxt = nextPrime(a) # If next is not same as 'a' if (nxt != b): return False # If next is not same as 'c' if (nextPrime(b) != c): return False return True# Driver code for above functionsif (areAdjacentPrimes(11, 13, 19)): print("Yes"),else: print("No")# This code is contributed by NIKITA TIWARI. |
C#
// Java program to check given three numbers are// primes are not.using System;class GFG { public static bool isPrime(int n) { // check if n is a multiple of 2 if (n % 2 == 0) return false; // if not, then just check the odds for (int i = 3; i * i <= n; i += 2) if (n % i == 0) return false; return true; } // return next prime number public static int nextPrime(int start) { // start with next number. int next = start + 1; // breaks after finding next prime number while (!isPrime(next)) next++; return next; } // check given three numbers are adjacent primes are // not. public static bool areAdjacentPrimes(int a, int b, int c) { // check given three numbers are primes are not. if (!isPrime(a) || !isPrime(b) || !isPrime(c)) return false; // find next prime of a int next = nextPrime(a); // If next is not same as 'a' if (next != b) return false; // If next is not same as 'c' if (nextPrime(b) != c) return false; return true; } // Driver code public static void Main() { if (areAdjacentPrimes(11, 13, 19)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// |
Javascript
<script>// JavaScript program to check given // three numbers are// primes are not. function isPrime(n) { // check if n is a multiple of 2 if (n % 2 == 0) return false; // if not, then just check the odds for (let i = 3; i * i <= n; i += 2) if (n % i == 0) return false; return true; } // return next prime number function nextPrime(start) { // start with next number. let next = start + 1; // breaks after finding next prime number while (!isPrime(next)) next++; return next; } // check given three numbers are // adjacent primes are not. function areAdjacentPrimes(a, b, c) { // check given three numbers are primes are not. if (!isPrime(a) || !isPrime(b) || !isPrime(c)) return false; // find next prime of a let next = nextPrime(a); // If next is not same as 'a' if (next != b) return false; // If next is not same as 'c' if (nextPrime(b) != c) return false; return true; } // Driver code if (areAdjacentPrimes(11, 13, 19)) document.write("Yes"); else document.write("No"); </script> |
PHP
<?php// PHP program to check given // three numbers are primes or not.// checks whether given // number is prime or not.function isPrime($n){ // check if n is // a multiple of 2 if ($n % 2 == 0) return false; // if not, then just // check the odds for ($i = 3; $i * $i <= $n; $i += 2) if ($n % $i == 0) return false; return true;}// return next prime numberfunction nextPrime($start){ // start with next number. $next = $start + 1; // breaks after finding // next prime number while (!isPrime($next)) $next++; return $next;}// check given three numbers// are adjacent primes are not.function areAdjacentPrimes($a, $b, $c){ // check given three numbers // are primes are not. if (!isPrime($a) || !isPrime($b) || !isPrime($c)) return false; // find next prime of a $next = nextPrime($a); // If next is not same as 'a' if ($next != $b) return false; // If next is // not same as 'c' if (nextPrime($b) != $c) return false; return true;}// Driver code if (areAdjacentPrimes(11, 13, 19)) echo "Yes";else echo "No";// This article is contributed by mits?> |
Output
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;// Function to generate all prime numbers up to 'n'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;}// Function to check if three given numbers are adjacent// primes or notbool areAdjacentPrimes(int a, int b, int c){ // Generate all prime numbers up to maximum of the three // given numbers int maxNum = max(max(a, b), c); vector<int> primes = generatePrimes(maxNum); // Find the index of a, b, and c in the list of prime // numbers 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(); // Check if a, b, and c are adjacent primes or not if (indexA + 1 == indexB && indexB + 1 == indexC) { return true; } else { return false; }}// Driver code for above functionsint 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 { // Function to generate all prime numbers up to 'n' 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; } // Function to check if three given numbers are adjacent primes or not private static boolean areAdjacentPrimes(int a, int b, int c) { // Generate all prime numbers up to the maximum of the three given numbers int maxNum = Math.max(Math.max(a, b), c); List<Integer> primes = generatePrimes(maxNum); // Find the index of a, b, and c in the list of prime numbers int indexA = primes.indexOf(a); int indexB = primes.indexOf(b); int indexC = primes.indexOf(c); // Check if a, b, and c are adjacent primes or not if (indexA + 1 == indexB && indexB + 1 == indexC) { return true; } else { return false; } } // Driver code for above functions public static void main(String[] args) { if (areAdjacentPrimes(11, 13, 19)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
# Function to generate all prime numbers up to 'n'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# Function to check if three given numbers are adjacent# primes or notdef are_adjacent_primes(a, b, c): # Generate all prime numbers up to the maximum of the three given numbers max_num = max(a, b, c) primes = generate_primes(max_num) # Find the index of a, b, and c in the list of prime numbers index_a = primes.index(a) index_b = primes.index(b) index_c = primes.index(c) # Check if a, b, and c are adjacent primes or not if index_a + 1 == index_b and index_b + 1 == index_c: return True else: return False# Driver code for above functionsif __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 { // Function to generate all prime numbers up to 'n' 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; } // Function to check if three given numbers are adjacent // primes or not static bool AreAdjacentPrimes(int a, int b, int c) { // Generate all prime numbers up to the maximum of // the three given numbers int maxNum = Math.Max(Math.Max(a, b), c); List<int> primes = GeneratePrimes(maxNum); // Find the index of a, b, and c in the list of // prime numbers int indexA = primes.IndexOf(a); int indexB = primes.IndexOf(b); int indexC = primes.IndexOf(c); // Check if a, b, and c are adjacent primes or not if (indexA + 1 == indexB && indexB + 1 == indexC) { return true; } else { return false; } } // Driver code for the above functions static void Main(string[] args) { if (AreAdjacentPrimes(11, 13, 19)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }} |
Javascript
// Function to generate all prime numbers up to 'n'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 to check if three given numbers are adjacent// primes or notfunction areAdjacentPrimes(a, b, c) { // Generate all prime numbers up to maximum of the three // given numbers const maxNum = Math.max(a, b, c); const primes = generatePrimes(maxNum); // Find the index of a, b, and c in the list of prime // numbers const indexA = primes.indexOf(a); const indexB = primes.indexOf(b); const indexC = primes.indexOf(c); // Check if a, b, and c are adjacent primes or not if (indexA + 1 === indexB && indexB + 1 === indexC) { return true; } else { return false; }}// Driver code for above functionsif (areAdjacentPrimes(11, 13, 19)) { console.log("Yes");} else { console.log("No");} |
Output
No
Time complexity: O(Logn)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
