Given four integers X, Y, X2%P, Y2%P, where P is a prime number. The task is to find prime P.
Note: Answer always exists.
Examples:
Input : X = 3, XsqmodP = 0, Y = 5, YsqmodP = 1
Output : 3
When x = 3, x2 = 9, and 9 modulo P is 0. So possible value of p is 3
When x = 5, x2 = 25, and 25 modulo P is 1. So possible value of p is 3
Input : X = 4, XsqmodP = 1, Y = 5, YsqmodP = 0
Output : 5
Approach :
From above numbers we get,
X2 – XsqmodP = 0 mod P
Y2 – YsqmodP = 0 mod P
Now find all the common prime factors from both the equation, and check if it satisfies the original equation, If it does (one of them will since answer always exists) then that’s the answer.
Below is the implementation of the above approach :
C++
// CPP program to possible prime number#include <bits/stdc++.h>using namespace std;// Function to check if a // number is prime or notbool Prime(int n){ for (int j = 2; j <= sqrt(n); j++) if (n % j == 0) return false; return true; }// Function to find possible prime numberint find_prime(int x, int xsqmodp , int y, int ysqmodp){ int n = x*x - xsqmodp; int n1 = y*y - ysqmodp; // Find a possible prime number for (int j = 2; j <= max(sqrt(n), sqrt(n1)); j++) { if (n % j == 0 && (x * x) % j == xsqmodp && n1 % j == 0 && (y * y) % j == ysqmodp) if (Prime(j)) return j; int j1 = n / j; if (n % j1 == 0 && (x * x) % j1 == xsqmodp && n1 % j1 == 0 && (y * y) % j1 == ysqmodp) if (Prime(j1)) return j1; j1 = n1 / j; if (n % j1 == 0 && (x * x) % j1 == xsqmodp && n1 % j1 == 0 && (y * y) % j1 == ysqmodp) if (Prime(j1)) return j1; } // Last condition if (n == n1) return n;}// Driver codeint main(){ int x = 3, xsqmodp = 0, y = 5, ysqmodp = 1; // Function call cout << find_prime(x, xsqmodp, y, ysqmodp); return 0;} |
Java
// Java program to possible prime numberimport java.util.*;class GFG{// Function to check if a // number is prime or notstatic boolean Prime(int n){ for (int j = 2; j <= Math.sqrt(n); j++) if (n % j == 0) return false; return true; }// Function to find possible prime numberstatic int find_prime(int x, int xsqmodp , int y, int ysqmodp){ int n = x * x - xsqmodp; int n1 = y * y - ysqmodp; // Find a possible prime number for (int j = 2; j <= Math.max(Math.sqrt(n), Math.sqrt(n1)); j++) { if (n % j == 0 && (x * x) % j == xsqmodp && n1 % j == 0 && (y * y) % j == ysqmodp) if (Prime(j)) return j; int j1 = n / j; if (n % j1 == 0 && (x * x) % j1 == xsqmodp && n1 % j1 == 0 && (y * y) % j1 == ysqmodp) if (Prime(j1)) return j1; j1 = n1 / j; if (n % j1 == 0 && (x * x) % j1 == xsqmodp && n1 % j1 == 0 && (y * y) % j1 == ysqmodp) if (Prime(j1)) return j1; } // Last condition if (n == n1) return n; return Integer.MIN_VALUE;}// Driver codepublic static void main(String[] args) { int x = 3, xsqmodp = 0, y = 5, ysqmodp = 1; // Function call System.out.println(find_prime(x, xsqmodp, y, ysqmodp));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to possible prime numberfrom math import sqrt# Function to check if a # number is prime or notdef Prime(n): for j in range(2, int(sqrt(n)) + 1, 1): if (n % j == 0): return False return True# Function to find possible prime numberdef find_prime(x, xsqmodp, y, ysqmodp): n = x * x - xsqmodp n1 = y * y - ysqmodp # Find a possible prime number for j in range(2, max(int(sqrt(n)), int(sqrt(n1))), 1): if (n % j == 0 and (x * x) % j == xsqmodp and n1 % j == 0 and (y * y) % j == ysqmodp): if (Prime(j)): return j j1 = n // j if (n % j1 == 0 and (x * x) % j1 == xsqmodp and n1 % j1 == 0 and (y * y) % j1 == ysqmodp): if (Prime(j1)): return j1 j1 = n1 // j if (n % j1 == 0 and (x * x) % j1 == xsqmodp and n1 % j1 == 0 and (y * y) % j1 == ysqmodp): if (Prime(j1)): return j1 # Last condition if (n == n1): return n# Driver codeif __name__ == '__main__': x = 3 xsqmodp = 0 y = 5 ysqmodp = 1 # Function call print(find_prime(x, xsqmodp, y, ysqmodp))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to possible prime numberusing System;class GFG{// Function to check if a // number is prime or notstatic bool Prime(int n){ for (int j = 2; j <= Math.Sqrt(n); j++) if (n % j == 0) return false; return true; }// Function to find possible prime numberstatic int find_prime(int x, int xsqmodp , int y, int ysqmodp){ int n = x * x - xsqmodp; int n1 = y * y - ysqmodp; // Find a possible prime number for (int j = 2; j <= Math.Max(Math.Sqrt(n), Math.Sqrt(n1)); j++) { if (n % j == 0 && (x * x) % j == xsqmodp && n1 % j == 0 && (y * y) % j == ysqmodp) if (Prime(j)) return j; int j1 = n / j; if (n % j1 == 0 && (x * x) % j1 == xsqmodp && n1 % j1 == 0 && (y * y) % j1 == ysqmodp) if (Prime(j1)) return j1; j1 = n1 / j; if (n % j1 == 0 && (x * x) % j1 == xsqmodp && n1 % j1 == 0 && (y * y) % j1 == ysqmodp) if (Prime(j1)) return j1; } // Last condition if (n == n1) return n; return int.MinValue;}// Driver codepublic static void Main() { int x = 3, xsqmodp = 0, y = 5, ysqmodp = 1; // Function call Console.WriteLine(find_prime(x, xsqmodp, y, ysqmodp));}}// This code is contributed by anuj_67.. |
Javascript
<script>// Javascript program to possible prime number// Function to check if a // number is prime or notfunction Prime(n){ for (let j = 2; j <= Math.sqrt(n); j++) if (n % j == 0) return false; return true; }// Function to find possible prime numberfunction find_prime(x, xsqmodp , y, ysqmodp){ let n = x*x - xsqmodp; let n1 = y*y - ysqmodp; // Find a possible prime number for (let j = 2; j <= Math.max(Math.sqrt(n), Math.sqrt(n1)); j++) { if (n % j == 0 && (x * x) % j == xsqmodp && n1 % j == 0 && (y * y) % j == ysqmodp) if (Prime(j)) return j; let j1 = parseInt(n / j); if (n % j1 == 0 && (x * x) % j1 == xsqmodp && n1 % j1 == 0 && (y * y) % j1 == ysqmodp) if (Prime(j1)) return j1; j1 = n1 / j; if (n % j1 == 0 && (x * x) % j1 == xsqmodp && n1 % j1 == 0 && (y * y) % j1 == ysqmodp) if (Prime(j1)) return j1; } // Last condition if (n == n1) return n;}// Driver code let x = 3, xsqmodp = 0, y = 5, ysqmodp = 1; // Function call document.write(find_prime(x, xsqmodp, y, ysqmodp));</script> |
Output:
3
Time Complexity: O(sqrt(n)2)
Auxiliary Space: O(1)
