Primitive root:
Given a prime number P, find the smallest primitive root of P and the total number of primitive roots of P. We define a primitive root of prime number P to be some integer g E [1,p-1] satisfying the property that all values of g*mod p where x E [0,p-2] are different (unique).
Input Format
A single prime integer denoting p.
Constraints
2<p<109
Output Format
Print two space-separated integers on a new line, where the first value is the smallest primitive root of p and the second value is the total number of primitive roots of p.
Sample Input
7
Sample Output
32
Explanation
The primitive roots of p-7 are 3 and 5, and no other numbers in [1,6] satisfy our definition of a primitive root. We then print the smallest primitive root (3) followed by the total number of primitive roots (2).
Sample input
9
Sample output
2 2
Program:
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool is_prime(int n) {
if (n <= 1)
return false;
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
return false;
return true;
}
int smallest_primitive_root(int p) {
for (int i = 2; i < p; i++) {
bool is_primitive_root = true;
for (int j = 1; j < p - 1; j++)
if (fmod(pow(i, j), p) == 1) {
is_primitive_root = false;
break;
}
if (is_primitive_root)
return i;
}
return -1;
}
int num_primitive_roots(int p) {
int phi = p - 1;
int num_roots = 0;
for (int i = 2; i < p; i++) {
bool is_primitive_root = true;
for (int j = 1; j < phi; j++)
if (fmod(pow(i, j), p) == 1) {
is_primitive_root = false;
break;
}
if (is_primitive_root)
num_roots++;
}
return num_roots;
}
int main() {
int p;
scanf("%d", &p);
if (!is_prime(p))
return 0;
int g = smallest_primitive_root(p);
int num = num_primitive_roots(p);
printf("%d %d\n", g, num);
}
/*
After completion of the code just click on submit not on compile and test code because it is not working but you just click on submit, it is getting submitted.
*/
Explanation:
This code defines three functions and uses them to compute and output the smallest primitive root and the number of primitive roots of a given prime number p.
The is_prime function takes an integer n and returns true if n is a prime number, and false otherwise. It first checks if n is less than or equal to 1, in which case it returns false. Then, it loops through all integers i from 2 to the square root of n. If n is divisible by i, it means n is not a prime number, so the function returns false. Otherwise, it continues looping until all potential divisors have been checked, at which point it returns true.
The smallest_primitive_root function takes a prime number p and returns the smallest positive integer g such that g is a primitive root modulo p. A primitive root modulo p is an integer g such that every non-zero integer modulo p can be expressed as a power of g. To find the smallest primitive root of p, the function loops through all integers from 2 to p-1, and checks whether each integer is a primitive root by verifying that i^j is not congruent to 1 modulo p for all j from 1 to p-2. If i is a primitive root, the function returns i. If no primitive root is found, the function returns -1.
The num_primitive_roots function takes a prime number p and returns the number of primitive roots modulo p. To compute this, the function first calculates Euler's totient function phi(p) = p-1, which is the number of positive integers less than p that are coprime to p. Then, the function loops through all integers from 2 to p-1, and checks whether each integer is a primitive root by verifying that i^j is not congruent to 1 modulo p for all j from 1 to phi(p)-1. If i is a primitive root, the function increments a counter variable. After all potential primitive roots have been checked, the function returns the counter value.
In the main function, the code first reads in the prime number p from the user. If p is not prime, the program terminates. Otherwise, it calls the smallest_primitive_root and num_primitive_roots functions to compute the smallest primitive root and the number of primitive roots of p, and prints these values to the console.
0 Comments