Come verificare se il numero può essere rappresentato in prima potenza (nth root è primo o no)

Question

Sto provando questo problema per un po 'ma ricevo risposte sbagliate ancora e ancora. Il numero può essere molto grande < = 2^2014. 22086. Prime Power Test

Spiegazione mio algoritmo:

1. Per un numero dato sto controllando se il numero può essere rappresentata come forma di potere primo o no.
2. Così il limite massimo per verificare la potenza principale è log n base 2.
3. Infine problema ridotto di trovare radice ennesima di un numero e se è il primo noi abbiamo la nostra risposta altrimenti verificare la presenza di tutti i i fino log (n base 2) e exit .
4. Ho usato tutti i tipi di ottimizzazioni e ho testato enormi casi di test e per tutti il ​​mio algoritmo fornisce la risposta corretta
5. ma Judge dice una risposta sbagliata.
6. Spoj avere un altro problema simile con piccole vincoli n < = 10^18 per il quale ho già avuto accettato con Python e C++ (miglior risolutore in C++)

Ecco il mio codice python Si prega di suggerire me se io sono fare qualcosa di sbagliato non sono molto abile in python quindi il mio algoritmo è un po 'lungo. Grazie in anticipo.

mio algoritmo:

import math 
import sys 
import fractions 
import random 
import decimal 
write = sys.stdout.write 
def sieve(n): 
    sqrtn = int(n**0.5) 
    sieve = [True] * (n+1) 
    sieve[0] = False 
    sieve[1] = False 
    for i in range(2, sqrtn+1): 
     if sieve[i]: 
      m = n//i - i 
      sieve[i*i:n+1:i] = [False] * (m+1) 
    return sieve 
def gcd(a, b): 
    while b: 
     a, b = b, a%b 
    return a 
def mr_pass(a, s, d, n): 
    a_to_power = pow(a, d, n) 
    if a_to_power == 1: 
     return True 
    for i in range(s-1): 
     if a_to_power == n - 1: 
      return True 
     a_to_power = (a_to_power * a_to_power) % n 
    return a_to_power == n - 1 
isprime=sieve(1000000) 
sprime= [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997] 
def smooth_num(n): 
    c=0 
    for a in sprime: 
     if(n%a==0): 
      c+=1 
     if(c>=2): 
      return True; 
    return False 
def is_prime(n): 
    if(n<1000000): 
     return isprime[n] 
    if any((n % p) == 0 for p in sprime): 
     return False 
    if n==2: 
     return True 
    d = n - 1 
    s = 0 
    while d % 2 == 0: 
     d >>= 1 
     s += 1 
    for repeat in range(10): 
     a=random.randint(1,n-1) 
     if not mr_pass(a, s, d, n): 
      return False 
    return True 
def iroot(n,k): 
    hi = 1 
    while pow(hi, k) < n: 
     hi *= 2 
    lo = hi // 2 
    while hi - lo > 1: 
     mid = (lo + hi) // 2 
     midToK = (mid**k) 
     if midToK < n: 
      lo = mid 
     elif n < midToK: 
      hi = mid 
     else: 
      return mid 
    if (hi**k) == n: 
     return hi 
    else: 
     return lo 
def isqrt(x): 
    n = int(x) 
    if n == 0: 
     return 0 
    a, b = divmod(n.bit_length(), 2) 
    x = pow(2,(a+b)) 
    while True: 
     y = (x + n//x)>>1 
     if y >= x: 
      return x 
     x = y 
maxx=2**1024;minn=2**64 
def nth_rootp(n,k): 
    return int(round(math.exp(math.log(n)/k),0)) 
def main(): 
    for cs in range(int(input())): 
     n=int(sys.stdin.readline().strip()) 
     if(smooth_num(n)): 
      write("Invalid order\n") 
      continue; 
     order = 0;m=0 
     power =int(math.log(n,2)) 
     for i in range(1,power+1): 
      if(n<=maxx): 
       if i==1:m=n 
       elif(i==2):m=isqrt(n) 
       elif(i==4):m=isqrt(isqrt(n)) 
       elif(i==8):m=isqrt(isqrt(isqrt(n))) 
       elif(i==16):m=isqrt(isqrt(isqrt(isqrt(n)))) 
       elif(i==32):m=isqrt(isqrt(isqrt(isqrt(isqrt(n))))) 
       elif(i==64):m=isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(n)))))) 
       elif(i==128):m=isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(n))))))) 
       elif(i==256):m=isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(n)))))))) 
       else:m=int(nth_rootp(n,i)) 
      else: 
       if i==1:m=n 
       elif i==2:m=isqrt(n) 
       elif(i==4):m=isqrt(isqrt(n)) 
       elif(i==8):m=isqrt(isqrt(isqrt(n))) 
       elif(i==16):m=isqrt(isqrt(isqrt(isqrt(n)))) 
       elif(i==32):m=isqrt(isqrt(isqrt(isqrt(isqrt(n))))) 
       elif(i==64):m=isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(n)))))) 
       elif(i==128):m=isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(n))))))) 
       elif(i==256):m=isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(isqrt(n)))))))) 
       else:m=iroot(n,i) 
      if m<2: 
       order=0 
       break 
      if(is_prime(m) and n==(m**i)): 
       write("%d %d\n"%(m,i)) 
       order = 1 
       break 
     if(order==0): 
      write("Invalid order\n") 
main() 

Answer 1

questo non è davvero una risposta, ma non ho abbastanza spazio per scrivere come un commento.

Quindi, se ancora non risolto il problema, si può provare la seguente funzione per nth_rootp, anche se è un po 'brutto (si tratta solo di una ricerca binaria per trovare il valore esatto della funzione):

def nth_rootp(n,k): 
    r = int(round(math.log(n,2)/k)) 
    left = 2**(r-1) 
    right = 2**(r+1) 
    if left**k == n: 
     return left 
    if right**k == n: 
     return right 
    while left**k < n and right**k > n: 
     tmp = (left + right)/2 
     if tmp**k == n: 
      return tmp 
     if tmp == left or tmp == right: 
      return tmp 
     if tmp**k < n: 
      left = tmp 
     else: 
      if tmp**k > n: 
       right = tmp 

Answer 2

Non leggerò tutto il codice, anche se sospetto che il problema sia l'inesattezza in virgola mobile. Ecco il mio programma per determinare se un numero n è una potenza primaria; restituisce il primo p e la potenza k:

# prime power predicate 

from random import randint 
from fractions import gcd 

def findWitness(n, k=5): # miller-rabin 
    s, d = 0, n-1 
    while d % 2 == 0: 
     s, d = s+1, d/2 
    for i in range(k): 
     a = randint(2, n-1) 
     x = pow(a, d, n) 
     if x == 1 or x == n-1: continue 
     for r in range(1, s): 
      x = (x * x) % n 
      if x == 1: return a 
      if x == n-1: break 
     else: return a 
    return 0 

# returns p,k such that n=p**k, or 0,0 
# assumes n is an integer greater than 1 
def primePower(n): 
    def checkP(n, p): 
     k = 0 
     while n > 1 and n % p == 0: 
      n, k = n/p, k + 1 
     if n == 1: return p, k 
     else: return 0, 0 
    if n % 2 == 0: return checkP(n, 2) 
    q = n 
    while True: 
     a = findWitness(q) 
     if a == 0: return checkP(n, q) 
     d = gcd(pow(a,q,n)-a, q) 
     if d == 1 or d == q: return 0, 0 
     q = d 

Il programma utilizza Piccolo Teorema di Fermat e sfrutta il testimone un alla compostezza di n che si trova dall'algoritmo Miller-Rabin . Viene fornito come Algoritmo 1.7.5 nel libro di Henri Cohen Corso in Teoria del numero algebrico computazionale. È possibile vedere il programma in azione al http://ideone.com/cNzQYr.

Answer 3

vostro look codice come un po 'troppo complicata per questo compito, non si preoccupa di controllare, ma la cosa che serve sono le seguenti

1. is_prime, naturalmente
2. un generatore privilegiata, opzionale
3. calcolare la radice ennesima di un numero in modo preciso

per il primo Consiglio forma deterministica della Miller-Rabin test con un appropriato set di witness da garantire un risultato esatto fino 1543267864443420616877677640751301 (1.543 x 10) per i numeri ancora più grandi è possibile utilizzare il probabilistica uno o utilizzare un elenco più grande di testimonianza scelto a tuoi criteri

con tutto ciò che un modello per il la soluzione è la seguente

import math 

def is_prime(n): 
    ... 

def sieve(n): 
    "list of all primes p such that p<n" 
    ... 

def inthroot(x,n): 
    "calculate floor(x**(1/n))" 
    ... 

def is_a_power(n): 
    "return (a,b) if n=a**b otherwise throw ValueError" 
    for b in sieve(math.log2(n) +1): 
     a = inthroot(n,b) 
     if a**b == n: 
      return a,b 
    raise ValueError("is not a power") 

def smooth_factorization(n): 
    "return (p,e) where p is prime and n = p**e if such value exists, otherwise throw ValueError" 
    e=1 
    p=n 
    while True: 
     try: 
      p,n = is_a_power(p) 
      e = e*n 
     except ValueError: 
      break 
    if is_prime(p): 
     return p,e 
    raise ValueError 

def main(): 
    for test in range(int(input())): 
     try: 
      p,e = smooth_factorization(int(input())) 
      print(p,e) 
     except ValueError: 
      print("Invalid order") 

main() 

E il codice di cui sopra dovrebbe essere autoesplicativo

Riempire i neri

0.123.516,41 mila

Come si conosce il test di Miller-Rabin, menzionerò solo che se sei interessato puoi trovare un'implementazione della versione deterministica here, basta aggiornare l'elenco di witness e sei pronto per partire.

Per la sieve, basta cambiare quello che si utilizza per restituire un elenco con il numero di numeri primi in questo modo per esempio [ p for p,is_p in enumerate(sieve) if is_p ]

Con quelli di mezzo, l'unica cosa rimasta è calcolare la ennesima radice di il numero e per farlo in modo preciso abbiamo bisogno di strappare quella fastidiosa aritmetica in virgola mobile che produce solo mal di testa, e la risposta è implementare lo Nth root algorithm usando solo aritmetica intera, che è molto simile a quella di isqrt che già uso, mi guida con quello fatto da Mark Dickinson per la radice cubica e generalizzare e ottengo questo

def inthroot(A, n) : 
    "calculate floor(A**(1/n))" 
    #https://en.wikipedia.org/wiki/Nth_root_algorithm 
    #https://en.wikipedia.org/wiki/Nth_root#nth_root_algorithm 
    #https://stackoverflow.com/questions/35254566/wrong-answer-in-spoj-cubert/35276426#35276426 
    #https://stackoverflow.com/questions/39560902/imprecise-results-of-logarithm-and-power-functions-in-python/39561633#39561633 
    if A<0: 
     if n%2 == 0: 
      raise ValueError 
     return - inthroot(-A,n) 
    if A==0: 
     return 0 
    n1 = n-1 
    if A.bit_length() < 1024: # float(n) safe from overflow 
     xk = int(round(pow(A,1.0/n))) 
     xk = (n1*xk + A//pow(xk,n1))//n # Ensure xk >= floor(nthroot(A)). 
    else: 
     xk = 1 << -(-A.bit_length()//n) # 1 << sum(divmod(A.bit_length(),n)) 
             # power of 2 closer but greater than the nth root of A 
    while True: 
     sig = A // pow(xk,n1) 
     if xk <= sig: 
      return xk 
     xk = (n1*xk + sig)//n 

e con tutto quanto sopra è possibile risolvere il problema senza scomodo