Given a prime 
. The task is to count all the primitive roots of .
A primitive root is an integer x (1 <= x < p) such that none of the integers x – 1, x2 – 1, …., xp – 2 – 1 are divisible by but xp – 1 – 1 is divisible by .
Examples:
Input: P = 3
Output: 1
The only primitive root modulo 3 is 2.
Input: P = 5
Output: 2
Primitive roots modulo 5 are 2 and 3.
Approach: There is always at least one primitive root for all primes. So, using Eulers totient function we can say that f(p-1) is the required answer where f(n) is euler totient function.
Below is the implementation of the above approach:
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 pint countPrimitiveRoots(int p){ int result = 1; for (int i = 2; i < p; i++) if (__gcd(i, p) == 1) result++; return result;}// Driver codeint main(){ int p = 5; cout << countPrimitiveRoots(p - 1); return 0;} |
Java
// Java program to find the number of// primitive roots modulo primeimport 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 pstatic 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 primefrom math import gcd# Function to return the count of# primitive roots modulo pdef countPrimitiveRoots(p): result = 1 for i in range(2, p, 1): if (gcd(i, p) == 1): result += 1 return result# Driver codeif __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 pfunction 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 pfunction countPrimitiveRoots(p){ var result = 1; for (var i = 2; i < p; i++) if (__gcd(i, p) == 1) result++; return result;}// Driver codevar p = 5;document.write( countPrimitiveRoots(p - 1));</script> |
Output:
2
Time Complexity: O(p * log(min(a, b))), where a and b are two parameters of gcd.
Auxiliary Space: O(log(min(a, b)))
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!
