Given an integer N and a base number A, the task is to check whether N is a Euler Pseudoprime to the given base A.
An integer N is called Euler Pseudoprime to the base A, if
- A > 0 and N is an odd composite number.
- A and N are co-prime i.e. GCD(A, N) = 1.
- A(N – 1) / 2 % N is either 1 or N – 1.
Examples:
Input: N = 121, A = 3
Output: Yes
Input: N = 343, A = 2
Output: No
Approach: Check all the given conditions for Euler Pseudoprime. If any one of the conditions is not true then print No else print Yes.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if n is compositebool isComposite(int n){ // Check if there is any divisor of n. // we only need check divisor till sqrt(n) // because if there is divisor which is greater // than sqrt(n) then there must be a divisor // which is less than sqrt(n) for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return true; } return false;}// Iterative Function to calculate// (x^y) % p in O(log y)int Power(int x, int y, int p){ // Initialize result int res = 1; // Update x if it is greater // than or equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) { res = (res * x) % p; } // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Function that returns true if N is// Euler Pseudoprime to the base Abool isEulerPseudoprime(int N, int A){ // Invalid base if (A <= 0) return false; // N is not a composite odd number if (N % 2 == 0 || !isComposite(N)) return false; // If A and N are not coprime if (__gcd(A, N) != 1) return false; int mod = Power(A, (N - 1) / 2, N); if (mod != 1 && mod != N - 1) return false; // All the conditions for Euler // Pseudoprime are satisfied return true;}// Driver codeint main(){ int N = 121, A = 3; if (isEulerPseudoprime(N, A)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachclass GFG {// Function that returns true if n is compositestatic boolean isComposite(int n){ // Check if there is any divisor of n. // we only need check divisor till sqrt(n) // because if there is divisor which is greater // than sqrt(n) then there must be a divisor // which is less than sqrt(n) for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return true; } return false;}// Iterative Function to calculate// (x^y) % p in O(log y)static int Power(int x, int y, int p){ // Initialize result int res = 1; // Update x if it is greater // than or equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) { res = (res * x) % p; } // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Function that returns true if N is// Euler Pseudoprime to the base Astatic boolean isEulerPseudoprime(int N, int A){ // Invalid base if (A <= 0) return false; // N is not a composite odd number if (N % 2 == 0 || !isComposite(N)) return false; // If A and N are not coprime if (__gcd(A, N) != 1) return false; int mod = Power(A, (N - 1) / 2, N); if (mod != 1 && mod != N - 1) return false; // All the conditions for Euler // Pseudoprime are satisfied return true;}static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver codepublic static void main(String []args) { int N = 121, A = 3; if (isEulerPseudoprime(N, A)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for nth Fuss–Catalan Number from math import gcd, sqrt# Function that returns true if n is composite def isComposite(n) : # Check if there is any divisor of n. # we only need check divisor till sqrt(n) # because if there is divisor which is greater # than sqrt(n) then there must be a divisor # which is less than sqrt(n) for i in range(2, int(sqrt(n)) + 1) : if (n % i == 0) : return True; return False; # Iterative Function to calculate # (x^y) % p in O(log y) def Power(x, y, p) : # Initialize result res = 1; # Update x if it is greater # than or equal to p x = x % p; while (y > 0) : # If y is odd, multiply x with result if (y & 1) : res = (res * x) % p; # y must be even now y = y >> 1; # y = y/2 x = (x * x) % p; return res; # Function that returns true if N is # Euler Pseudoprime to the base A def isEulerPseudoprime(N, A) : # Invalid base if (A <= 0) : return False; # N is not a composite odd number if (N % 2 == 0 or not isComposite(N)) : return False; # If A and N are not coprime if (gcd(A, N) != 1) : return false; mod = Power(A, (N - 1) // 2, N); if (mod != 1 and mod != N - 1) : return False; # All the conditions for Euler # Pseudoprime are satisfied return True; # Driver code if __name__ == "__main__" : N = 121; A = 3; if (isEulerPseudoprime(N, A)) : print("Yes"); else : print("No");# This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG{// Function that returns true if n is compositestatic bool isComposite(int n){ // Check if there is any divisor of n. // we only need check divisor till sqrt(n) // because if there is divisor which is greater // than sqrt(n) then there must be a divisor // which is less than sqrt(n) for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) return true; } return false;}// Iterative Function to calculate// (x^y) % p in O(log y)static int Power(int x, int y, int p){ // Initialize result int res = 1; // Update x if it is greater // than or equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) { res = (res * x) % p; } // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}// Function that returns true if N is// Euler Pseudoprime to the base Astatic bool isEulerPseudoprime(int N, int A){ // Invalid base if (A <= 0) return false; // N is not a composite odd number if (N % 2 == 0 || !isComposite(N)) return false; // If A and N are not coprime if (__gcd(A, N) != 1) return false; int mod = Power(A, (N - 1) / 2, N); if (mod != 1 && mod != N - 1) return false; // All the conditions for Euler // Pseudoprime are satisfied return true;}static int __gcd(int a, int b) { if (b == 0) return a; return __gcd(b, a % b); } // Driver codepublic static void Main(String []args) { int N = 121, A = 3; if (isEulerPseudoprime(N, A)) Console.WriteLine("Yes"); else Console.WriteLine("No");}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation of the approach// Function that returns true if n is compositefunction isComposite(n){ // Check if there is any divisor of n. // we only need check divisor till sqrt(n) // because if there is divisor which is greater // than sqrt(n) then there must be a divisor // which is less than sqrt(n) for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return true; } return false;}// Iterative Function to calculate// (x^y) % p in O(log y)function Power(x, y, p) { // Initialize result let res = 1; // Update x if it is greater // than or equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) { res = (res * x) % p; } // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res;}function __gcd(a, b) { if (b == 0) return a; return __gcd(b, a % b);}// Function that returns true if N is// Euler Pseudoprime to the base Afunction isEulerPseudoprime(N, A) { // Invalid base if (A <= 0) return false; // N is not a composite odd number if (N % 2 == 0 || !isComposite(N)) return false; // If A and N are not coprime if (__gcd(A, N) != 1) return false; let mod = Power(A, (N - 1) / 2, N); if (mod != 1 && mod != N - 1) return false; // All the conditions for Euler // Pseudoprime are satisfied return true;}// Driver codelet N = 121, A = 3;if (isEulerPseudoprime(N, A)) document.write("Yes");else document.write("No");// This code is contributed by _saurabh_jaiswal</script> |
Output:
Yes
Time Complexity: O(sqrt(N))
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!
