Posted on by Kalkicode
Code Mathematics

# 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
}
}
}
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
}
}``````

#### 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
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
}
}
}
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
}
}``````

#### 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
}
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
}
}
}
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
}
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
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() :
#  Euclid Series
#  3, 7, 31, 211, 2311, 30031, 510511, 9699691
#  223092871, 6469693231 ..
#  Test Cases

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_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
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()
#  Euclid Series
#  3, 7, 31, 211, 2311, 30031, 510511, 9699691
#  223092871, 6469693231 ..
#  Test Cases
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
}
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
}
}``````

#### 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
}
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
}``````

#### 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``````

## 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.

Categories
Relative Post