Find all the divisors of a number using Python

Question

I am trying to write a Python script that will find prime numbers. In the way that I am going about this, the script is going to take a number from a range, determine the factors, determine if the only two factors are 1 and itself, and return true if it's a prime number. I need help with my code to find the factors.

num = int(input("enter: "))

i = 1

while i < num:
  if num % i == 0:
    print(i)
    i += 1
  else:
    pass

The i is set to 1 because you can't divide by 0. However, the return starts to work, however, it only returns a couple of numbers, not the full list that I am hoping for. For example, you input 20, it returns only 1 and 2.

To be clear, you're trying to find all *divisors* of a number, not all *multiples*. There are an infinite number number of *multiples* for every `num` aside from `0`, so "finding them all" is nonsensical; `num * ∞` is a multiple of `num` (ignoring the weirdness involved with infinity, where any multiple of infinity remains infinity; you get the idea), as are the infinite multiples of `num` between `num * 0` and `num * ∞`. — ShadowRanger, Mar 03 '20 at 17:38
Side-note: If your goal is to identify prime numbers, you don't need to compute *all* factors of `num`. Just start looking for factors at 2 (ideally special-casing 2, then testing only odd numbers from 3 up to the square root of `num` to avoid excessive work), and if you find a *single* factor, stop; you already know it's composite, not prime. There are more efficient ways than trial division, especially if you need to determine primality for many numbers, but reducing ~`num` checks done every time to a *maximum* of `√num / 2` checks (usually far less) gets a big improvement for little effort. — ShadowRanger, Mar 03 '20 at 17:55

score 1 · Accepted Answer · answered Mar 03 '20 at 17:34

1

You're only incrementing i in the "is even" case. This'd fix it:

num = int(input("enter: "))

i = 1

while i < num:
  if num % i == 0:
    print(i)
  i += 1

However, it's better to use range() for iterating over a range of numbers:

num = int(input("enter: "))
for i in range(1, num):
  if num % i == 0:
    print(i)

answered Mar 03 '20 at 17:34

AKX

152,115
15
115
172

Side-note: On why it's better to use `range`: One, it's simpler (one line with all logic embedded in it, versus three spread out). Two, it's safer (`continue` or `if` statements can't accidentally skip an increment). Three, it's faster; simple math operations have one of the highest overhead:work done ratios in CPython (because `int`s are objects, and the math itself involves constantly loading, unpacking them to C types, doing the work, then repacking, using many (8) byte code ops); `range` dramatically reduces that overhead, by doing more work at the C layer, with fewer (2) byte code ops. – ShadowRanger Mar 03 '20 at 17:41
Thank you! I know it was more of an easy solution, I'm only just a beginner, but I really appreciate it! It gave me the ability to push forward, though I also figured out that because of the inclusion of the range, I think have to add 1 to the num to find the prime numbers. But thank you! – gumbo_hopkins Mar 03 '20 at 17:49
@gumbo_hopkins: You don't need to add `1` to `num`; `range` excludes the `stop` value (`num`), so you won't be testing `num` itself to determine if it's a divisor of `num`, but that's trivially true anyway, and not relevant to primality testing (being divisible by yourself doesn't make you composite). Your original loop was excluding `num` anyway (because it tested `i < num`, not `i <= num`), so the `range` is precisely equivalent (but simpler/faster) than the fixed `while` loop. – ShadowRanger Mar 03 '20 at 17:57

Find all the divisors of a number using Python

1 Answers1