Skip to main content

Check whether the given number is euclid number or not

Euclid numbers are a sequence of positive integers that are generated using the formula:

E(n) = p1p2p3...pn + 1

where p1, p2, p3, ..., pn are the first n prime numbers. In other words, Euclid numbers are of the form 2^p - 1, where p is a prime number.

Euclid numbers are named after the ancient Greek mathematician Euclid, who proved that there are infinitely many prime numbers. Euclid himself did not define or study these numbers, but they were named after him due to their connection to prime numbers.

The first few Euclid numbers are:

E(1) = 3
E(2) = 7
E(3) = 31
E(4) = 127
E(5) = 8191
E(6) = 131071
E(7) = 524287
E(8) = 2147483647
E(9) = 2305843009213693951
E(10) = 618970019642690137449562111

Euclid numbers are rare and quickly become very large as n increases. They have been studied in number theory and have applications in cryptography, where they are used as part of the RSA encryption algorithm.

The Sieve of Eratosthenes is an efficient algorithm for finding all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime number, starting from 2. At the end of the algorithm, the unmarked numbers are all prime.

To solve the problem of checking whether a given number is an Euclid number using the Sieve of Eratosthene.

Program Solution

/*
  Java Program for
  Check whether the given number is euclid number or not
*/
import java.util.HashSet;
public class EuclidNumber
{
	public HashSet < Integer > record;
	public int limit;
	public EuclidNumber()
	{
		this.limit = 1000000;
		this.record = new HashSet < Integer > ();
		// Collecting the initial prime number
		this.sieveOfEratosthenes(this.limit);
	}
	// Find all prime numbers which have smaller and equal to given number n
	public void sieveOfEratosthenes(int n)
	{
		if (n <= 1)
		{
			// When n are invalid to prime number 
			return;
		}
		// This are used to detect prime numbers
		boolean[] prime = new boolean[n + 1];
		// Loop controlling variables
		int i = 0;
		int j = 1;
		// Initial two numbers are not prime (0 and 1)
		prime[i] = false;
		prime[j] = false;
		// Set the initial (2 to n element is prime)
		for (i = 2; i <= n; ++i)
		{
			prime[i] = true;
		}
		// Initial 0 and 1 are not prime
		// We start to 2
		for (i = 2; i * i <= n; ++i)
		{
			if (prime[i] == true)
			{
				// When i is prime number
				// Modify the prime status of all next multiplier of location i
				for (j = i * i; j <= n; j += i)
				{
					prime[j] = false;
				}
			}
		}
		int product = 1;
		// Collecting prime numbers
		for (i = 0; i <= n; ++i)
		{
			if (prime[i] == true)
			{
				product = product * i;
				// When i is prime
				record.add(product + 1);
			}
		}
	}
	public void isEuclidNo(int number)
	{
		if (number > this.limit)
		{
			// 10,00000 is maximum limit 
			System.out.println(" Given number are exceed limit");
			return;
		}
		if (number > 0 && record.contains(number))
		{
			System.out.println(" Number " + number + " is Euclid Number");
		}
		else
		{
			System.out.println(" Number " + number + " is not Euclid Number");
		}
	}
	public static void main(String[] args)
	{
		EuclidNumber task = new EuclidNumber();
		// Euclid Series	
		// 3, 7, 31, 211, 2311, 30031, 510511, 9699691 
		// 223092871, 6469693231 ..
		// Test Cases
		task.isEuclidNo(209);
		task.isEuclidNo(510511);
		task.isEuclidNo(2311);
		task.isEuclidNo(131);
		task.isEuclidNo(30031);
	}
}

input

 Number 209 is not Euclid Number
 Number 510511 is Euclid Number
 Number 2311 is Euclid Number
 Number 131 is not Euclid Number
 Number 30031 is Euclid Number
// Include header file
#include <iostream>

#include <set>

using namespace std;
class EuclidNumber
{
	public: set < int > record;
	int limit; 
	EuclidNumber()
	{
		this->limit = 1000000;
		this->sieveOfEratosthenes(this->limit);
	}
	// Find all prime numbers which have smaller and equal to given number n
	void sieveOfEratosthenes(int n)
	{
		if (n <= 1)
		{
			// When n are invalid to prime number 
			return;
		}
		// This are used to detect prime numbers
		bool prime[n + 1];
		// Loop controlling variables
		int i = 0;
		int j = 1;
		// Initial two numbers are not prime (0 and 1)
		prime[i] = false;
		prime[j] = false;
		// Set the initial (2 to n element is prime)
		for (i = 2; i <= n; ++i)
		{
			prime[i] = true;
		}
		// Initial 0 and 1 are not prime
		// We start to 2
		for (i = 2; i *i <= n; ++i)
		{
			if (prime[i] == true)
			{
				// When i is prime number
				// Modify the prime status of all next multiplier of location i
				for (j = i *i; j <= n; j += i)
				{
					prime[j] = false;
				}
			}
		}
		int product = 1;
		// Collecting prime numbers
		for (i = 0; i <= n; ++i)
		{
			if (prime[i] == true)
			{
				product = product *i;
				// When i is prime
				this->record.insert(product + 1);
			}
		}
	}
	void isEuclidNo(int number)
	{
		if (number > this->limit)
		{
			// 10,00000 is maximum limit 
			cout << " Given number are exceed limit" << endl;
			return;
		}
		if (number > 0 && this->record.find(number) != this->record.end())
		{
			cout << " Number " << number << " is Euclid Number" << endl;
		}
		else
		{
			cout << " Number " << number << " is not Euclid Number" << endl;
		}
	}
};
int main()
{
	EuclidNumber *task = new EuclidNumber();
	// Euclid Series	
	// 3, 7, 31, 211, 2311, 30031, 510511, 9699691 
	// 223092871, 6469693231 ..
	// Test Cases
	task->isEuclidNo(209);
	task->isEuclidNo(510511);
	task->isEuclidNo(2311);
	task->isEuclidNo(131);
	task->isEuclidNo(30031);
	return 0;
}

input

 Number 209 is not Euclid Number
 Number 510511 is Euclid Number
 Number 2311 is Euclid Number
 Number 131 is not Euclid Number
 Number 30031 is Euclid Number
// Include namespace system
using System;
using System.Collections.Generic;
public class EuclidNumber
{
	public HashSet < int > record;
	public int limit;
	public EuclidNumber()
	{
		this.limit = 1000000;
		this.record = new HashSet < int > ();
		// Collecting the initial prime number
		this.sieveOfEratosthenes(this.limit);
	}
	// Find all prime numbers which have smaller and equal to given number n
	public void sieveOfEratosthenes(int n)
	{
		if (n <= 1)
		{
			// When n are invalid to prime number 
			return;
		}
		// This are used to detect prime numbers
		Boolean[] prime = new Boolean[n + 1];
		// Loop controlling variables
		int i = 0;
		int j = 1;
		// Initial two numbers are not prime (0 and 1)
		prime[i] = false;
		prime[j] = false;
		// Set the initial (2 to n element is prime)
		for (i = 2; i <= n; ++i)
		{
			prime[i] = true;
		}
		// Initial 0 and 1 are not prime
		// We start to 2
		for (i = 2; i * i <= n; ++i)
		{
			if (prime[i] == true)
			{
				// When i is prime number
				// Modify the prime status of all next multiplier of location i
				for (j = i * i; j <= n; j += i)
				{
					prime[j] = false;
				}
			}
		}
		int product = 1;
		// Collecting prime numbers
		for (i = 0; i <= n; ++i)
		{
			if (prime[i] == true)
			{
				product = product * i;
				// When i is prime
				this.record.Add(product + 1);
			}
		}
	}
	public void isEuclidNo(int number)
	{
		if (number > this.limit)
		{
			// 10,00000 is maximum limit 
			Console.WriteLine(" Given number are exceed limit");
			return;
		}
		if (number > 0 && this.record.Contains(number))
		{
			Console.WriteLine(" Number " + number + " is Euclid Number");
		}
		else
		{
			Console.WriteLine(" Number " + number + " is not Euclid Number");
		}
	}
	public static void Main(String[] args)
	{
		EuclidNumber task = new EuclidNumber();
		// Euclid Series	
		// 3, 7, 31, 211, 2311, 30031, 510511, 9699691 
		// 223092871, 6469693231 ..
		// Test Cases
		task.isEuclidNo(209);
		task.isEuclidNo(510511);
		task.isEuclidNo(2311);
		task.isEuclidNo(131);
		task.isEuclidNo(30031);
	}
}

input

 Number 209 is not Euclid Number
 Number 510511 is Euclid Number
 Number 2311 is Euclid Number
 Number 131 is not Euclid Number
 Number 30031 is Euclid Number
<?php
class EuclidNumber
{
	public $record;
	public $limit;
	public	function __construct()
	{
		$this->limit = 1000000;
		$this->record = array();
		$this->sieveOfEratosthenes($this->limit);
	}
	// Find all prime numbers which have smaller and equal to given number n
	public	function sieveOfEratosthenes($n)
	{
		if ($n <= 1)
		{
			// When n are invalid to prime number 
			return;
		}
		// This are used to detect prime numbers
		$prime = array_fill(0, $n + 1, true);
		// Loop controlling variables
		$i = 0;
		$j = 1;
		// Initial two numbers are not prime (0 and 1)
		$prime[$i] = false;
		$prime[$j] = false;
		// Initial 0 and 1 are not prime
		// We start to 2
		for ($i = 2; $i * $i <= $n; ++$i)
		{
			if ($prime[$i] == true)
			{
				// When i is prime number
				// Modify the prime status of all next multiplier of location i
				for ($j = $i * $i; $j <= $n; $j += $i)
				{
					$prime[$j] = false;
				}
			}
		}
		$product = 1;
		// Collecting prime numbers
		for ($i = 0; $i <= $n; ++$i)
		{
			if ($prime[$i] == true)
			{
				$product = $product * $i;
				// When i is prime
				$this->record[] = $product + 1;
			}
		}
	}
	public	function isEuclidNo($number)
	{
		if ($number > $this->limit)
		{
			// 10,00000 is maximum limit 
			echo " Given number are exceed limit".
			"\n";
			return;
		}
		if ($number > 0 && in_array($number, $this->record, TRUE))
		{
			echo " Number ".$number.
			" is Euclid Number".
			"\n";
		}
		else
		{
			echo " Number ".$number.
			" is not Euclid Number".
			"\n";
		}
	}
}

function main()
{
	$task = new EuclidNumber();
	// Euclid Series	
	// 3, 7, 31, 211, 2311, 30031, 510511, 9699691 
	// 223092871, 6469693231 ..
	// Test Cases
	$task->isEuclidNo(209);
	$task->isEuclidNo(510511);
	$task->isEuclidNo(2311);
	$task->isEuclidNo(131);
	$task->isEuclidNo(30031);
}
main();

input

 Number 209 is not Euclid Number
 Number 510511 is Euclid Number
 Number 2311 is Euclid Number
 Number 131 is not Euclid Number
 Number 30031 is Euclid Number

class EuclidNumber
{
	constructor()
	{
		this.limit = 1000000;
		this.record = new Set();
		this.sieveOfEratosthenes(this.limit);
	}
	// Find all prime numbers which have smaller and equal to given number n
	sieveOfEratosthenes(n)
	{
		if (n <= 1)
		{
			// When n are invalid to prime number 
			return;
		}
		// This are used to detect prime numbers
		var prime = Array(n + 1).fill(true);
		// Loop controlling variables
		var i = 0;
		var j = 1;
		// Initial two numbers are not prime (0 and 1)
		prime[i] = false;
		prime[j] = false;
		// Initial 0 and 1 are not prime
		// We start to 2
		for (i = 2; i * i <= n; ++i)
		{
			if (prime[i] == true)
			{
				// When i is prime number
				// Modify the prime status of all next multiplier of location i
				for (j = i * i; j <= n; j += i)
				{
					prime[j] = false;
				}
			}
		}
		var product = 1;
		// Collecting prime numbers
		for (i = 0; i <= n; ++i)
		{
			if (prime[i] == true)
			{
				product = product * i;
				// When i is prime
				this.record.add(product + 1);
			}
		}
	}
	isEuclidNo(number)
	{
		if (number > this.limit)
		{
			// 10,00000 is maximum limit 
			console.log(" Given number are exceed limit");
			return;
		}
		if (number > 0 && this.record.has(number))
		{
			console.log(" Number " + number + " is Euclid Number");
		}
		else
		{
			console.log(" Number " + number + " is not Euclid Number");
		}
	}
}

function main()
{
	var task = new EuclidNumber();
	// Euclid Series	
	// 3, 7, 31, 211, 2311, 30031, 510511, 9699691 
	// 223092871, 6469693231 ..
	// Test Cases
	task.isEuclidNo(209);
	task.isEuclidNo(510511);
	task.isEuclidNo(2311);
	task.isEuclidNo(131);
	task.isEuclidNo(30031);
}
main();

input

 Number 209 is not Euclid Number
 Number 510511 is Euclid Number
 Number 2311 is Euclid Number
 Number 131 is not Euclid Number
 Number 30031 is Euclid Number
#  Python 3 Program for
#  Check whether the given number is euclid number or not
class EuclidNumber :
    def __init__(self) :
        self.limit = 100000
        self.record = set()
        self.sieveOfEratosthenes(self.limit)
    
    #  Find all prime numbers which have smaller and equal to given number n
    def sieveOfEratosthenes(self, n) :
        if (n <= 1) :
            #  When n are invalid to prime number 
            return
        
        prime = [True] * (n + 1)
        i = 0
        j = 1
        #  Initial two numbers are not prime (0 and 1)
        prime[i] = False
        prime[j] = False
        #  Initial 0 and 1 are not prime
        #  We start to 2
        i = 2
        while (i * i <= n) :
            if (prime[i] == True) :
                #  When i is prime number
                #  Modify the prime status of all next multiplier of location i
                j = i * i
                while (j <= n) :
                    prime[j] = False
                    j += i
            i += 1
        
        product = 1
        #  Collecting prime numbers
        i = 0
        while (i <= n) :
            if (prime[i] == True) :
                product = product * i
                #  When i is prime
                self.record.add(product+1)
            i += 1
        
    
    def isEuclidNo(self, number) :
        if (number > self.limit) :
            #  100000 is maximum limit 
            print(" Given number are exceed limit")
            return
        
        if (number > 0 and number in self.record) :
            print(" Number ", number ," is Euclid Number")
        else :
            print(" Number ", number ," is not Euclid Number")
        
    

def main() :
    task = EuclidNumber()
    #  Euclid Series    
    #  3, 7, 31, 211, 2311, 30031, 510511, 9699691 
    #  223092871, 6469693231 ..
    #  Test Cases
    task.isEuclidNo(209)
    task.isEuclidNo(2311)
    task.isEuclidNo(131)
    task.isEuclidNo(30031)

if __name__ == "__main__": main()

input

 Number  209  is not Euclid Number
 Number  2311  is Euclid Number
 Number  131  is not Euclid Number
 Number  30031  is Euclid Number
require 'set'
#  Ruby Program for
#  Check whether the given number is euclid number or not
class EuclidNumber 
	# Define the accessor and reader of class EuclidNumber
	attr_reader :record, :limit
	attr_accessor :record, :limit
	def initialize() 
		self.limit = 100000
		self.record = SortedSet.new([])
		self.sieveOfEratosthenes(self.limit)
	end

	#  Find all prime numbers which have smaller and equal to given number n
	def sieveOfEratosthenes(n) 
		if (n <= 1) 
			#  When n are invalid to prime number 
			return
		end

		#  This are used to detect prime numbers
		prime = Array.new(n + 1) {true}
		#  Loop controlling variables
		i = 0
		j = 1
		#  Initial two numbers are not prime (0 and 1)
		prime[i] = false
		prime[j] = false
		#  Initial 0 and 1 are not prime
		#  We start to 2
		i = 2
		while (i * i <= n) 
			if (prime[i] == true) 
				#  When i is prime number
				#  Modify the prime status of all next multiplier of location i
				j = i * i
				while (j <= n) 
					prime[j] = false
					j += i
				end

			end

			i += 1
		end

		product = 1
		#  Collecting prime numbers
		i = 0
		while (i <= n) 
			if (prime[i] == true) 
				product = product * i
				#  When i is prime
				self.record.add(product + 1)
			end

			i += 1
		end

	end

	def isEuclidNo(number) 
		if (number > self.limit) 
			#  100000 is maximum limit 
			print(" Given number are exceed limit", "\n")
			return
		end

		if (number > 0 && self.record.include?(number)) 
			print(" Number ", number ," is Euclid Number", "\n")
		else 
			print(" Number ", number ," is not Euclid Number", "\n")
		end

	end

end

def main() 
	task = EuclidNumber.new()
	#  Euclid Series	
	#  3, 7, 31, 211, 2311, 30031, 510511, 9699691 
	#  223092871, 6469693231 ..
	#  Test Cases
	task.isEuclidNo(209)
	task.isEuclidNo(2311)
	task.isEuclidNo(131)
	task.isEuclidNo(30031)
end

main()

input

 Number 209 is not Euclid Number
 Number 2311 is Euclid Number
 Number 131 is not Euclid Number
 Number 30031 is Euclid Number

import scala.collection.mutable._;
/*
  Scala Program for
  Check whether the given number is euclid number or not
*/
class EuclidNumber(var record: Set[Int] , var limit: Int)
	{
		
			def this()
			{
				this(Set(),1000000);
				this.sieveOfEratosthenes(this.limit);
			}
			// Find all prime numbers which have smaller and equal to given number n
			def sieveOfEratosthenes(n: Int): Unit = {
				if (n <= 1)
				{
					// When n are invalid to prime number 
					return;
				}
				// This are used to detect prime numbers
				var prime: Array[Boolean] = Array.fill[Boolean](n + 1)(true);
				// Loop controlling variables
				var i: Int = 0;
				var j: Int = 1;
				// Initial two numbers are not prime (0 and 1)
				prime(i) = false;
				prime(j) = false;
				// Initial 0 and 1 are not prime
				// We start to 2
				i = 2;
				while (i * i <= n)
				{
					if (prime(i) == true)
					{
						// When i is prime number
						// Modify the prime status of all next multiplier of location i
						j = i * i;
						while (j <= n)
						{
							prime(j) = false;
							j += i;
						}
					}
					i += 1;
				}
				var product: Int = 1;
				// Collecting prime numbers
				i = 0;
				while (i <= n)
				{
					if (prime(i) == true)
					{
						product = product * i;
						// When i is prime
						record.add(product + 1);
					}
					i += 1;
				}
			}
			def isEuclidNo(number: Int): Unit = {
				if (number > this.limit)
				{
					// 10,00000 is maximum limit 
					println(" Given number are exceed limit");
					return;
				}
				if (number > 0 && record.contains(number))
				{
					println(" Number " + number + " is Euclid Number");
				}
				else
				{
					println(" Number " + number + " is not Euclid Number");
				}
			}
		}
		object Main
		{
			def main(args: Array[String]): Unit = {
				var task: EuclidNumber = new EuclidNumber();
				// Euclid Series	
				// 3, 7, 31, 211, 2311, 30031, 510511, 9699691 
				// 223092871, 6469693231 ..
				// Test Cases
				task.isEuclidNo(209);
				task.isEuclidNo(510511);
				task.isEuclidNo(2311);
				task.isEuclidNo(131);
				task.isEuclidNo(30031);
			}
		}

input

 Number 209 is not Euclid Number
 Number 510511 is Euclid Number
 Number 2311 is Euclid Number
 Number 131 is not Euclid Number
 Number 30031 is Euclid Number
/*
  Kotlin Program for
  Check whether the given number is euclid number or not
*/
class EuclidNumber
{
	var record: MutableSet <Int> ;
	var limit: Int;
		constructor()
		{
			this.limit = 1000000;
			this.record =  mutableSetOf <Int> ();
			this.sieveOfEratosthenes(this.limit);
		}
		// Find all prime numbers which have smaller and equal to given number n
		fun sieveOfEratosthenes(n: Int): Unit
		{
			if (n <= 1)
			{
				// When n are invalid to prime number 
				return;
			}
			// This are used to detect prime numbers
			val prime: Array < Boolean > = Array(n + 1)
			{
				true
			};
			// Loop controlling variables
			var i: Int = 0;
			var j: Int = 1;
			// Initial two numbers are not prime (0 and 1)
			prime[i] = false;
			prime[j] = false;
			i = 2;
			while (i * i <= n)
			{
				if (prime[i] == true)
				{
					j = i * i;
					while (j <= n)
					{
						prime[j] = false;
						j += i;
					}
				}
				i += 1;
			}
			var product: Int = 1;
			i = 0;
			while (i <= n)
			{
				if (prime[i] == true)
				{
					product = product * i;
					// When i is prime
					this.record.add(product + 1);
				}
				i += 1;
			}
		}
		fun isEuclidNo(number: Int): Unit
		{
			if (number > this.limit)
			{
				// 10,00000 is maximum limit 
				println(" Given number are exceed limit");
				return;
			}
			if (number > 0 && this.record.contains(number))
			{
				println(" Number " + number + " is Euclid Number");
			}
			else
			{
				println(" Number " + number + " is not Euclid Number");
			}
		}
	}
	fun main(args: Array < String > ): Unit
	{
		val task: EuclidNumber = EuclidNumber();
		// Euclid Series	
		// 3, 7, 31, 211, 2311, 30031, 510511, 9699691 
		// 223092871, 6469693231 ..
		// Test Cases
		task.isEuclidNo(209);
		task.isEuclidNo(510511);
		task.isEuclidNo(2311);
		task.isEuclidNo(131);
		task.isEuclidNo(30031);
	}

input

 Number 209 is not Euclid Number
 Number 510511 is Euclid Number
 Number 2311 is Euclid Number
 Number 131 is not Euclid Number
 Number 30031 is Euclid Number
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment