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