• API
• FAQ
• Tools
• Archive
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.

Top