Dado un primo . La tarea es contar todas las raíces primitivas de .
Una raíz primitiva es un número entero x (1 <= x < p) tal que ninguno de los números enteros x – 1, x 2 – 1, … ., x p – 2 – 1 son divisibles por x p – 1 – 1 es divisible por .
Ejemplos:
Entrada: P = 3
Salida: 1
La única raíz primitiva módulo 3 es 2.
Entrada: P = 5
Salida: 2 Las
raíces primitivas módulo 5 son 2 y 3.
Enfoque: siempre hay al menos una raíz primitiva para todos los números primos. Entonces, usando la función totient de Euler podemos decir que f(p-1) es la respuesta requerida donde f(n) es la función totient de Euler.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the number of // primitive roots modulo prime #include <bits/stdc++.h> using namespace std; // Function to return the count of // primitive roots modulo p int countPrimitiveRoots(int p) { int result = 1; for (int i = 2; i < p; i++) if (__gcd(i, p) == 1) result++; return result; } // Driver code int main() { int p = 5; cout << countPrimitiveRoots(p - 1); return 0; }
Java
// Java program to find the number of // primitive roots modulo prime import java.io.*; class GFG { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to return the count of // primitive roots modulo p static int countPrimitiveRoots(int p) { int result = 1; for (int i = 2; i < p; i++) if (__gcd(i, p) == 1) result++; return result; } // Driver code public static void main (String[] args) { int p = 5; System.out.println( countPrimitiveRoots(p - 1)); } } // This code is contributed by anuj_67..
Python3
# Python 3 program to find the number # of primitive roots modulo prime from math import gcd # Function to return the count of # primitive roots modulo p def countPrimitiveRoots(p): result = 1 for i in range(2, p, 1): if (gcd(i, p) == 1): result += 1 return result # Driver code if __name__ == '__main__': p = 5 print(countPrimitiveRoots(p - 1)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find the number of // primitive roots modulo prime using System; class GFG { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to return the count of // primitive roots modulo p static int countPrimitiveRoots(int p) { int result = 1; for (int i = 2; i < p; i++) if (__gcd(i, p) == 1) result++; return result; } // Driver code static public void Main (String []args) { int p = 5; Console.WriteLine( countPrimitiveRoots(p - 1)); } } // This code is contributed by Arnab Kundu
PHP
<?php // PHP program to find the number of // primitive roots modulo prime // Recursive function to return // gcd of a and b function __gcd($a, $b) { // Everything divides 0 if ($a == 0) return b; if ($b == 0) return $a; // base case if ($a == $b) return $a; // a is greater if ($a > $b) return __gcd($a - $b, $b); return __gcd($a, $b - $a); } // Function to return the count of // primitive roots modulo p function countPrimitiveRoots($p) { $result = 1; for ($i = 2; $i < $p; $i++) if (__gcd($i, $p) == 1) $result++; return $result; } // Driver code $p = 5; echo countPrimitiveRoots($p - 1); // This code is contributed by anuj_67 ?>
Javascript
<script> // Javascript program to find the number of // primitive roots modulo prime // Recursive function to return gcd of a and b function __gcd( a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to return the count of // primitive roots modulo p function countPrimitiveRoots(p) { var result = 1; for (var i = 2; i < p; i++) if (__gcd(i, p) == 1) result++; return result; } // Driver code var p = 5; document.write( countPrimitiveRoots(p - 1)); </script>
2
Complejidad de tiempo: O(p * log(min(a, b))), donde a y b son dos parámetros de gcd.
Espacio auxiliar: O(log(min(a, b)))
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA