Sort by

recency

|

826 Discussions

|

  • + 0 comments

    I highly recommend this insightful and thought-provoking piece to anyone seeking knowledge and a deeper understanding of the subject.

  • + 0 comments

    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)

  • + 0 comments

    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)
    
  • + 1 comment

    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

  • + 3 comments

    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.