SHARE
TWEET

Untitled

a guest May 23rd, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/bin/python3
  2. import math
  3.  
  4. def max_prime_factor(n):
  5.     maxPrime = -1
  6.    
  7.     # We keep dividing n by 2 to get rid of all the even composite factors.
  8.     while n % 2 == 0:
  9.         maxPrime = 2
  10.         n >>= 1 # equivalent to n //= 2
  11.    
  12.     # We loop over the possible odd factors.
  13.     # to remove the rest of the composites, and updating maxPrime to the largest factor.
  14.     for i in range(3, int(math.sqrt(n)) + 1, 2):
  15.         while n % i == 0:
  16.             maxPrime = i
  17.             n //= i
  18.    
  19.     # If at this stage n is is still bigger than 2
  20.     # then n must be prime so we return it, otherwise we return maxPrime
  21.     return n if n > 2 else maxPrime
  22.  
  23.  
  24. T = int(input().strip())
  25. for _ in range(T):
  26.     N = int(input().strip())
  27.     print(max_prime_factor(N))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top