We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Primitive Problem
Primitive Problem
Sort by
recency
|
826 Discussions
|
Please Login in order to post a comment
I highly recommend this insightful and thought-provoking piece to anyone seeking knowledge and a deeper understanding of the subject.
This solution with python , but has some test faild because of Time limit exceeded .
import math
import os
import random
import re
import sys
def power(x, y, p):
result = 1
x = x % p
while y > 0:
if y & 1:
result = (result * x) % p
y = y >> 1
x = (x * x) % p
return result
def is_primitive_root(g, p, factors):
for factor in factors:
if power(g, (p - 1) // factor, p) == 1:
return False
return True
def find_primitive_roots(p):
primitive_roots = []
factors = set()
# Find prime factors of p-1
for i in range(2, int(math.sqrt(p-1)) + 1):
if (p - 1) % i == 0:
factors.add(i)
factors.add((p - 1) // i)
for g in range(2, p):
if is_primitive_root(g, p, factors):
primitive_roots.append(g)
return primitive_roots
def smallest_primitive_root(p):
primitive_roots = find_primitive_roots(p)
return min(primitive_roots)
if name == 'main':
p = int(input().strip())
smallest_root = smallest_primitive_root(p)
total_roots = len(find_primitive_roots(p))
print(smallest_root, total_roots)
This solution with python , but has some test faild because of Time limit exceeded .
import math import os import random import re import sys
def power(x, y, p): result = 1 x = x % p while y > 0: if y & 1: result = (result * x) % p y = y >> 1 x = (x * x) % p return result
def is_primitive_root(g, p, factors): for factor in factors: if power(g, (p - 1) // factor, p) == 1: return False return True
def find_primitive_roots(p): primitive_roots = [] factors = set() # Find prime factors of p-1 for i in range(2, int(math.sqrt(p-1)) + 1): if (p - 1) % i == 0: factors.add(i) factors.add((p - 1) // i)
def smallest_primitive_root(p): primitive_roots = find_primitive_roots(p) return min(primitive_roots)
if name == 'main': p = int(input().strip())
To find the smallest primitive root and the total number of primitive roots for a given prime number, we can use mathematical concepts. Primitive roots are fascinating mathematical objects, and they play a crucial role in number theory
Absolutely, mathematics is a powerful tool that I often use for various purposes. It helps me understand probabilities and make informed decisions in various situations. Learning mathematics has been essential for me, as it has enabled me to develop critical thinking and problem-solving skills that I can apply in my everyday life and in various fields of study.