CODEWITHSUNDEEP
pythonfactors
M46
M46

Reputation: 43

Counting how many factors an integer has

So I have written a function to determine how many factors a number has and list that number. However my function is not outputting the correct information.

def num_factors(integer):
    result = 0
    for i in range(1,integer+1):
        if integer%i == 0:
            result +=1
    return result

print(num_factors(5))
print(num_factors(6))
print(num_factors(97))
print(num_factors(105))
print(num_factors(999))

For some reason it is outputting:

2
4
2
8
8

when it should be outputting:

0
2
0
6
6

Upvotes: 0

Views: 807

Answers (6)

dawg
dawg

Reputation: 103744

The issue is that you are counting division by 1 and the test integer itself.

You either need to subtract 2 or skip 1 and integer to get what you want as the desired output:

def num_factors(integer):
    result = 0
    for i in range(2,integer): # skips 1 and integer...
        if integer%i == 0:
            result +=1
    return result

And even better is to realize that for every x * y that is a factor of integer we only need to find one of them (ie, 16 has 2,4,and 8 as factors. Count 2 twice (2 x 8=16) and 4 once (4 x 4=16)) And since one will be less than or equal to the square root of integer just loop to the square root of integer and increment by 2 instead of by 1 and only make a fraction of the tests (and make the result 1000's of times faster):

def num_factors(integer):
    result = 0
    stop=int(float(integer)**0.5)
    for i in range(2,stop+1):
        if integer%i == 0:
            result +=2
    if stop*stop==integer: result-=1    
    return result

for x in (5,6,97,105,999):
    print(f'{x}: {num_factors(x)}')

Prints:

5: 0
6: 2
97: 0
105: 6
999: 6

BTW: It is, in fact, customary to count 1 and the integer itself as factors. So all these results should be +2 and your original solution was actually correct. To make the solutions above correct, just start with result=2

Upvotes: 1

Frank Yellin
Frank Yellin

Reputation: 11240

Okay, it's not really the question you're asking right now, but it may be your next question. Your algorithm works fine if your integer is small, but what about when your integer is large? Suppose integer = 1_200_000_000?

You need to find the prime factorization of the integer:

integer = p1**q1 * p2**q2 * p3**q3 * .....

and the number of factors (including 1 and the integer itself) is

(q1 + 1)(q2 + 1)(q3 + 1)....

Since 1,200,000,000 = (2**10)(3**1)(5**8), the number of factors is (11 * 2 * 8) = 176.

Upvotes: 0

Belhadjer Samir
Belhadjer Samir

Reputation: 1659

try this :

num_factors=lambda integer : len([e  for e in range(1,integer) if integer%e==0 and e not in [1,integer]])



print(num_factors(5))
print(num_factors(6))
print(num_factors(97))
print(num_factors(105))
print(num_factors(999))

Upvotes: 0

Chris Charley
Chris Charley

Reputation: 6573

sympy provides this function to find prime factors.

>>> from sympy.ntheory import factorint
>>> factorint(6008)   # 6008 = (2**3) * (751**1)
{2: 3, 751: 1}

Upvotes: 1

svit
svit

Reputation: 1

I would do it this way:

def num_factors(integer):
    for i in range(1, integer, 1):
        if integer % i == 0:
            print(i)

print(num_factors(5))
print(num_factors(6))
print(num_factors(97))
print(num_factors(105))
print(num_factors(999))

Upvotes: 0

XerneraC
XerneraC

Reputation: 66

With the line for i in range(1,integer+1): you are looping through all the numbers between 1 and your integer, including 1 and your integer, which are of course factors.

So for example if integer = 5, you'd loop over 1, 2, 3, 4, and 5. Out of these 1 and 5 are both of course factors of 5.

You could edit the line to for i in range(2,integer): to fix the error. The resulting code would look like this:

def num_factors(integer):
    result = 0
    for i in range(2,integer):
        if integer%i == 0:
            result +=1
    return result

print(num_factors(5))
print(num_factors(6))
print(num_factors(97))
print(num_factors(105))
print(num_factors(999))

Though as someone in the comments suggested, you could reduce the search space even more.

Upvotes: 1

Related Questions