Given a positive integer n, the task is to check if it is Euclid Number or not. Print ‘YES’ if the given number is Euclid Number otherwise print ‘NO’.
Euclid number : In Mathematics, Euclid numbers are integers of the form – 
where 
is product of first n prime numbers.
The first few Euclid numbers are-
3, 7, 31, 211, 2311, 30031, 510511, 9699691, ……….
Example:
Input: N = 31 Output: YES 31 can be expressed in the form of pn# + 1 as p3# + 1 (First 3 prime numbers are 2, 3, 5 and their product is 30 ) Input: N = 43 Output: NO 43 cannot be expressed in the form of pn# + 1
Naive Approach:
- Generate all prime number in the range using Sieve of Eratosthenes.
- Then starting from first prime (i.e 2 ) start multiplying next prime number and keep checking if product + 1 = n .
- If the product + 1 = n then, n is Euclid number. Otherwise not.
Below is the implementation of above approach:
C++
// CPP program to check Euclid Number#include <bits/stdc++.h>using namespace std;#define MAX 10000vector<int> arr;// Function to generate prime numbersvoid SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. bool prime[MAX]; memset(prime, true, sizeof(prime)); for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < MAX; i += p) prime[i] = false; } } // store all prime numbers // to vector 'arr' for (int p = 2; p < MAX; p++) if (prime[p]) arr.push_back(p);}// Function to check the number for Euclid Numberbool isEuclid(long n){ long long product = 1; int i = 0; while (product < n) { // Multiply next prime number // and check if product + 1 = n // holds or not product = product * arr[i]; if (product + 1 == n) return true; i++; } return false;}// Driver codeint main(){ // Get the prime numbers SieveOfEratosthenes(); // Get n long n = 31; // Check if n is Euclid Number if (isEuclid(n)) cout << "YES\n"; else cout << "NO\n"; // Get n n = 42; // Check if n is Euclid Number if (isEuclid(n)) cout << "YES\n"; else cout << "NO\n"; return 0;} |
Java
// Java program to check Euclid Numberimport java.util.*;class GFG { static final int MAX = 10000; static Vector<Integer> arr = new Vector<Integer>(); // Function to get the prime numbers static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. boolean[] prime = new boolean[MAX]; for (int i = 0; i < MAX; i++) prime[i] = true; for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < MAX; i += p) prime[i] = false; } } // store all prime numbers // to vector 'arr' for (int p = 2; p < MAX; p++) if (prime[p]) arr.add(p); } // Function to check the number for Euclid Number static boolean isEuclid(long n) { long product = 1; int i = 0; while (product < n) { // Multiply next prime number // and check if product + 1 = n // holds or not product = product * arr.get(i); if (product + 1 == n) return true; i++; } return false; } public static void main(String[] args) { // Get the prime numbers SieveOfEratosthenes(); // Get n long n = 31; // Check if n is Euclid Number if (isEuclid(n)) System.out.println("YES"); else System.out.println("NO"); // Get n n = 42; // Check if n is Euclid Number if (isEuclid(n)) System.out.println("YES"); else System.out.println("NO"); }} |
Python3
# Python 3 program to check # Euclid NumberMAX = 10000arr = []# Function to generate prime numbersdef SieveOfEratosthenes(): # Create a boolean array "prime[0..n]" # and initialize all entries it as # true. A value in prime[i] will # finally be false if i is Not a # prime, else true. prime = [True] * MAX p = 2 while p * p < MAX : # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p for i in range(p * 2, MAX, p): prime[i] = False p += 1 # store all prime numbers # to vector 'arr' for p in range(2, MAX): if (prime[p]): arr.append(p)# Function to check the number# for Euclid Numberdef isEuclid(n): product = 1 i = 0 while (product < n) : # Multiply next prime number # and check if product + 1 = n # holds or not product = product * arr[i] if (product + 1 == n): return True i += 1 return False# Driver codeif __name__ == "__main__": # Get the prime numbers SieveOfEratosthenes() # Get n n = 31 # Check if n is Euclid Number if (isEuclid(n)): print("YES") else: print("NO") # Get n n = 42 # Check if n is Euclid Number if (isEuclid(n)): print("YES") else: print("NO")# This code is contributed # by ChitraNayal |
C#
// C# program to check Euclid Numberusing System;using System.Collections.Generic;class GFG { static readonly int MAX = 10000; static List<int> arr = new List<int>(); // Function to get the prime numbers static void SieveOfEratosthenes() { // Create a boolean array // "prime[0..n]" and initialize // all entries it as true. // A value in prime[i] will // finally be false if i is // Not a prime, else true. bool[] prime = new bool[MAX]; for (int i = 0; i < MAX; i++) prime[i] = true; for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < MAX; i += p) prime[i] = false; } } // store all prime numbers // to vector 'arr' for (int p = 2; p < MAX; p++) if (prime[p]) arr.Add(p); } // Function to check the number for Euclid Number static bool isEuclid(long n) { long product = 1; int i = 0; while (product < n) { // Multiply next prime number // and check if product + 1 = n // holds or not product = product * arr[i]; if (product + 1 == n) return true; i++; } return false; } // Driver code public static void Main(String[] args) { // Get the prime numbers SieveOfEratosthenes(); // Get n long n = 31; // Check if n is Euclid Number if (isEuclid(n)) Console.WriteLine("YES"); else Console.WriteLine("NO"); // Get n n = 42; // Check if n is Euclid Number if (isEuclid(n)) Console.WriteLine("YES"); else Console.WriteLine("NO"); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript program to check Euclid Numbervar MAX = 10000;var arr = [];// Function to generate prime numbersfunction SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. var prime = Array(MAX).fill(true);; for (var p = 2; p * p < MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p for (var i = p * 2; i < MAX; i += p) prime[i] = false; } } // store all prime numbers // to vector 'arr' for (var p = 2; p < MAX; p++) if (prime[p]) arr.push(p);}// Function to check the number for Euclid Numberfunction isEuclid( n){ var product = 1; var i = 0; while (product < n) { // Multiply next prime number // and check if product + 1 = n // holds or not product = product * arr[i]; if (product + 1 == n) return true; i++; } return false;}// Driver code// Get the prime numbersSieveOfEratosthenes();// Get nvar n = 31;// Check if n is Euclid Numberif (isEuclid(n)) document.write("YES<br>");else document.write("NO<br>"); // Get nn = 42;// Check if n is Euclid Numberif (isEuclid(n)) document.write("YES<br>");else document.write("NO<br>");// This code is contributed by itsok.</script> |
Output:
YES NO
Note: Above approach will take O(Pn#) for each query (for every N) i.e. no. of prime numbers to be multiplied to check if n is Euclid number or not.
Auxiliary Space: O(n)
Efficient Approach:
- Generate all prime number in the range using Sieve of Eratosthenes.
- Compute prefix product of prime numbers up to a range to avoid re-calculating the product using hash table.
- If the product + 1 = n then, n is Euclid number. Otherwise not.
Below is the implementation of above approach:
C++
// CPP program to check Euclid Number#include <bits/stdc++.h>using namespace std;#define MAX 10000unordered_set<long long int> s;// Function to generate the Prime numbers// and store their productsvoid SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. bool prime[MAX]; memset(prime, true, sizeof(prime)); for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < MAX; i += p) prime[i] = false; } } // store prefix product of prime numbers // to unordered_set 's' long long int product = 1; for (int p = 2; p < MAX; p++) { if (prime[p]) { // update product by multiplying // next prime product = product * p; // insert 'product+1' to set s.insert(product + 1); } }}// Function to check the number for Euclid Numberbool isEuclid(long n){ // Check if number exist in // unordered set or not // If exist, return true if (s.find(n) != s.end()) return true; else return false;}// Driver codeint main(){ // Get the prime numbers SieveOfEratosthenes(); // Get n long n = 31; // Check if n is Euclid Number if (isEuclid(n)) cout << "YES\n"; else cout << "NO\n"; // Get n n = 42; // Check if n is Euclid Number if (isEuclid(n)) cout << "YES\n"; else cout << "NO\n"; return 0;} |
Java
// Java program to check Euclid Numberimport java.util.*;class GFG {static int MAX = 10000;static HashSet<Integer> s = new HashSet<Integer>();// Function to generate the Prime numbers// and store their productsstatic void SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false // if i is Not a prime, else true. boolean []prime = new boolean[MAX]; Arrays.fill(prime, true); prime[0] = false; prime[1] = false; for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < MAX; i += p) prime[i] = false; } } // store prefix product of prime numbers // to unordered_set 's' int product = 1; for (int p = 2; p < MAX; p++) { if (prime[p]) { // update product by multiplying // next prime product = product * p; // insert 'product+1' to set s.add(product + 1); } }}// Function to check the number for Euclid Numberstatic boolean isEuclid(int n){ // Check if number exist in // unordered set or not // If exist, return true if (s.contains(n)) return true; else return false;}// Driver codepublic static void main(String[] args){ // Get the prime numbers SieveOfEratosthenes(); // Get n int n = 31; // Check if n is Euclid Number if (isEuclid(n)) System.out.println("Yes"); else System.out.println("No"); // Get n n = 42; // Check if n is Euclid Number if (isEuclid(n)) System.out.println("Yes"); else System.out.println("No");}} // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to check Euclid Number MAX = 10000s = set() # Function to generate the Prime numbers # and store their products def SieveOfEratosthenes(): # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is Not a prime, else true. prime = [True] * (MAX) prime[0], prime[1] = False, False for p in range(2, 100): # If prime[p] is not changed, # then it is a prime if prime[p] == True: # Update all multiples of p for i in range(p * 2, MAX, p): prime[i] = False # store prefix product of prime numbers # to unordered_set 's' product = 1 for p in range(2, MAX): if prime[p] == True: # update product by multiplying # next prime product = product * p # insert 'product+1' to set s.add(product + 1) # Function to check the number # for Euclid Number def isEuclid(n): # Check if number exist in # unordered set or not # If exist, return true if n in s: return True else: return False# Driver code if __name__ == "__main__": # Get the prime numbers SieveOfEratosthenes() # Get n n = 31 # Check if n is Euclid Number if isEuclid(n) == True: print("YES") else: print("NO") # Get n n = 42 # Check if n is Euclid Number if isEuclid(n) == True: print("YES") else: print("NO") # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG {static int MAX = 10000;static HashSet<int> s = new HashSet<int>();// Function to generate the Prime numbers// and store their productsstatic void SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false // if i is Not a prime, else true. Boolean []prime = new Boolean[MAX]; for (int p = 0; p < MAX; p++) prime[p] = true; prime[0] = false; prime[1] = false; for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < MAX; i += p) prime[i] = false; } } // store prefix product of prime numbers // to unordered_set 's' int product = 1; for (int p = 2; p < MAX; p++) { if (prime[p]) { // update product by multiplying // next prime product = product * p; // insert 'product+1' to set s.Add(product + 1); } }}// Function to check the number // for Euclid Numberstatic Boolean isEuclid(int n){ // Check if number exist in // unordered set or not // If exist, return true if (s.Contains(n)) return true; else return false;}// Driver codepublic static void Main(String[] args){ // Get the prime numbers SieveOfEratosthenes(); // Get n int n = 31; // Check if n is Euclid Number if (isEuclid(n)) Console.WriteLine("Yes"); else Console.WriteLine("No"); // Get n n = 42; // Check if n is Euclid Number if (isEuclid(n)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to check Euclid Number let MAX = 10000;let s = new Set();// Function to generate the Prime numbers// and store their productsfunction SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. // A value in prime[i] will finally be false // if i is Not a prime, else true. let prime = new Array(MAX); for(let i=0;i<prime.length;i++) { prime[i]=true; } prime[0] = false; prime[1] = false; for (let p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (let i = p * 2; i < MAX; i += p) prime[i] = false; } } // store prefix product of prime numbers // to unordered_set 's' let product = 1; for (let p = 2; p < MAX; p++) { if (prime[p]) { // update product by multiplying // next prime product = product * p; // insert 'product+1' to set s.add(product + 1); } }}// Function to check the number for Euclid Numberfunction isEuclid(n){ // Check if number exist in // unordered set or not // If exist, return true if (s.has(n)) return true; else return false;}// Driver code// Get the prime numbersSieveOfEratosthenes(); // Get nlet n = 31;// Check if n is Euclid Numberif (isEuclid(n)) document.write("Yes<br>");else document.write("No<br>");// Get nn = 42;// Check if n is Euclid Numberif (isEuclid(n)) document.write("Yes<br>");else document.write("No<br>"); // This code is contributed by avanitrachhadiya2155</script> |
Output:
YES NO
Note: Above approach will take O(1) time to answer a query.
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!