Prime factors, help understand the use of square root

user_13800260 0
Viewed 590

Following the solution given on geeks for geeks website for finding prime factors, I don't really follow why they use the square root of n on line 16 (for i in range(3,int(math.sqrt(n))+1,2): )

https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

# Python program to print prime factors 

import math 

# A function to print all prime factors of 
# a given number n 
def primeFactors(n): 
    
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        print 2, 
        n = n / 2
        
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
        
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            print i, 
            n = n / i 
            
    # Condition if n is a prime 
    # number greater than 2 
    if n > 2: 
        print n

this is the logic im having trouble following, if someone could understand the counter example given below.

Every composite number has at least one prime factor less than or equal to square root of itself. This property can be proved using counter statement. Let a and b be two factors of n such that a*b = n. If both are greater than √n, then a.b > √n, * √n, which contradicts the expression “a * b = n”.

prime-factoring logic math python-3.x python
1 Answers

It's simple arithmetic. If r is the square root of n, then r * r == n. If you multiply r by anything larger than it, the result will be larger than n. So there can't be any other prime factor larger than r.

So there's no point in continuing the loop past the square root, since it can never find anything there.

user_14918950
Related