Given a number N and a base number A. The task is to check whether the number is a Fermat Pseudoprime to the base.
The number N is called as Fermat Pseudoprime to the base A, if
1. A > 1
2. N is a composite number
3. N divides AN-1 – 1.
Examples:
Input : N = 645, a = 2
Output :1
645 = 3*5*43, Hence it is a composite number
Also 645 divides 2^(644)-1
Hence it is a Fermat Pseudoprime.
Input : N = 6, a = 2
Output :0
Approach: The approach is to check the below conditions:
- Check if A > 1.
- Check if N is a composite number.
- Check if N divides AN-1 – 1.
If all of the above conditions satisfy then N is a fermat pseudoprime to base A.
Below is the implementation of the above approach:
C++
// C++ program to check if N is Fermat pseudoprime// to the base A or not#include <bits/stdc++.h>using namespace std;// Function to check if the given number is compositebool checkcomposite(int n){ // Check if there is any divisor of n less than sqrt(n) for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return 1; } return 0;}// Effectively calculate (x^y) modulo modint power(int x, int y, int mod){ // Initialize result int res = 1; while (y) { // If power is odd, then update the answer if (y & 1) res = (res * x) % mod; // Square the number and reduce // the power to its half y = y >> 1; x = (x * x) % mod; } // Return the result return res;}// Function to check for Fermat Pseudoprimebool Check(int n, int a){ // If it is composite and satisfy Fermat criterion if (a>1 && checkcomposite(n) && power(a, n - 1, n) == 1) return 1; // Else return 0 return 0;}// Driver codeint main(){ int N = 645; int a = 2; // Function call cout << Check(N, a); return 0;} |
Java
// Java program to check if N is Fermat pseudoprime // to the base A or not class GFG { // Function to check if // the given number is composite static boolean checkcomposite(int n) { // Check if there is any divisor of n // less than sqrt(n) for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return true; } } return false; } // Effectively calculate (x^y) modulo mod static int power(int x, int y, int mod) { // Initialize result int res = 1; while (y != 0) { // If power is odd, // then update the answer if ((y & 1) == 1) { res = (res * x) % mod; } // Square the number and reduce // the power to its half y = y >> 1; x = (x * x) % mod; } // Return the result return res; } // Function to check for Fermat Pseudoprime static int Check(int n, int a) { // If it is composite and // satisfy Fermat criterion if (a > 1 && checkcomposite(n) && power(a, n - 1, n) == 1) { return 1; } // Else return 0 return 0; } // Driver Code public static void main(String[] args) { int N = 645; int a = 2; // Function call System.out.println(Check(N, a)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to check if N is Fermat pseudoprime# to the base A or notfrom math import sqrt# Function to check if the given number is compositedef checkcomposite(n): # Check if there is any divisor of n less than sqrt(n) for i in range(2,int(sqrt(n))+1,1): if (n % i == 0): return 1 return 0# Effectively calculate (x^y) modulo moddef power(x, y, mod): # Initialize result res = 1 while (y): # If power is odd, then update the answer if (y & 1): res = (res * x) % mod # Square the number and reduce # the power to its half y = y >> 1 x = (x * x) % mod # Return the result return res# Function to check for Fermat Pseudoprimedef Check(n,a): # If it is composite and satisfy Fermat criterion if (a>1 and checkcomposite(n) and power(a, n - 1, n) == 1): return 1 # Else return 0 return 0# Driver codeif __name__ == '__main__': N = 645 a = 2 # Function call print(Check(N, a))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to check if N is Fermat pseudoprime // to the base A or not using System;class GFG{ // Function to check if // the given number is composite static bool checkcomposite(int n) { // Check if there is any divisor of n // less than sqrt(n) for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) return true; } return false; } // Effectively calculate (x^y) modulo mod static int power(int x, int y, int mod) { // Initialize result int res = 1; while (y != 0) { // If power is odd, then update the answer if ((y & 1) == 1) res = (res * x) % mod; // Square the number and reduce // the power to its half y = y >> 1; x = (x * x) % mod; } // Return the result return res; } // Function to check for Fermat Pseudoprime static int Check(int n, int a) { // If it is composite and satisfy Fermat criterion if (a > 1 && checkcomposite(n) && power(a, n - 1, n) == 1) return 1; // Else return 0 return 0; } // Driver code static public void Main () { int N = 645; int a = 2; // Function call Console.WriteLine(Check(N, a)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript program to check if// N is Fermat pseudoprime// to the base A or not// Function to check if the given// number is compositefunction checkcomposite(n){ // Check if there is any divisor // of n less than sqrt(n) for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return 1; } return 0;}// Effectively calculate (x^y) modulo modfunction power(x, y, mod){ // Initialize result let res = 1; while (y) { // If power is odd, then update the answer if (y & 1) res = (res * x) % mod; // Square the number and reduce // the power to its half y = y >> 1; x = (x * x) % mod; } // Return the result return res;}// Function to check for Fermat Pseudoprimefunction Check(n, a){ // If it is composite and satisfy // Fermat criterion if (a>1 && checkcomposite(n) && power(a, n - 1, n) == 1) return 1; // Else return 0 return 0;}// Driver code let N = 645; let a = 2; // Function call document.write(Check(N, a));</script> |
Output:
1
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!