Encuentre el primo P usando cuatro enteros dados

Dados cuatro enteros X, Y, X ² %P, Y ² %P, donde P es un número primo. La tarea es encontrar el primo P.
Nota: La respuesta siempre existe.
Ejemplos:

Entrada: X = 3, XsqmodP = 0, Y = 5, YsqmodP = 1
Salida: 3
Cuando x = 3, x ² = 9 y 9 módulo P es 0. Entonces, el valor posible de p es 3
Cuando x = 5, x ² = 25, y 25 módulo P es 1. Entonces, el valor posible de p es 3
Entrada: X = 4, XsqmodP = 1, Y = 5, YsqmodP = 0
Salida: 5

Enfoque:
de los números anteriores obtenemos,

X ² – XsqmodP = 0 mod P
Y ² – YsqmodP = 0 mod P

Ahora encuentre todos los factores primos comunes de ambas ecuaciones y verifique si satisface la ecuación original. Si lo hace (uno de ellos lo hará, ya que la respuesta siempre existe), entonces esa es la respuesta.
A continuación se muestra la implementación del enfoque anterior:

C++

// CPP program to possible prime number
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a
// number is prime or not
bool Prime(int n)
{
    for (int j = 2; j <= sqrt(n); j++)
        if (n % j == 0)
            return false;
 
    return true;
}
 
 
// Function to find possible prime number
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 <= 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 code
int 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 number
import java.util.*;
class GFG
{
 
// Function to check if a
// number is prime or not
static 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 number
static 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 code
public 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 number
from math import sqrt
 
# Function to check if a
# number is prime or not
def 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 number
def 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 code
if __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 number
using System;
 
class GFG
{
 
// Function to check if a
// number is prime or not
static 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 number
static 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 code
public 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 not
function Prime(n)
{
    for (let j = 2; j <= Math.sqrt(n); j++)
        if (n % j == 0)
            return false;
 
    return true;
}
 
 
// Function to find possible prime number
function 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>

Producción:

Complejidad de tiempo: O(sqrt(n) ² )

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por ManishKhetan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta