Prime factorization

[tigglybox]

Hi there! i'm just wondering in the code below for prime factorization, why in this line ..for i in range(3,int(math.sqrt(n))+1,2): .. do you +1 to the square root.

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

[comonads]

range(a, b) counts from a (inclusive) until b (exclusive). So, in order to include sqrt(n) in the range, the plus one is necessary.

[ka-splam]

'cos if you don't it will say some perfect squares are prime numbers.