Are there any bugs or ways to make my divisor code better?

Question

After coding my divisor code which I did as a practice for my GCSE stuff which I have to take soon, I have decided to ask the community if there are any bugs or ways I can improve my code.

import time, math
from array import *
def programme():
    num = input("Enter your Number: ")
    try:
        intnum = int(num)
        if(intnum < 0):
            error("POSITIVE NUMBERS ONLY")
        else:
            numbers = array("i",[])
            starttimer = time.time()
            i = 1
            print("\nThe divisors of your number are:"),
            while i <= math.sqrt(intnum):
                if (intnum % i) == 0:
                    numbers.insert(0,i)
                    numbers.insert(0,int(intnum/i))
                    print(i,":", int(intnum/i))
                i += 1
            numbers = sorted(numbers, reverse = True)
            print("The Highest Proper Divisor Is\n--------\n",str(numbers[1]) , "\n--------\nIt took"  ,round(time.time() - starttimer, 2)  ,"seconds to finish finding the divisors." )
    except ValueError:
       error("NOT VALID NUMBER")
    except OverflowError:
       error("NUMBER IS TO LARGE")
    except:
       error("UNKNOWN ERROR")

def error(error):
    print("\n----------------------------------\nERROR - " + error + "\n----------------------------------\n")
running = True
while(running):
    programme()
    print("----------------------------------")
    restart = input("Do You Want Restart?")
    restart = restart.lower()
    if restart in ("yes", "y", "ok", "sure", ""):
        print("Restarting\n----------------------------------")
    else:
        print("closing Down")
        running = False

I don't care how small the improvement is all I want are ways in which I can make it better!

When inputting 262144 I get

Enter your Number: 262144

The divisors of your number are:
1 : 262144
2 : 131072
4 : 65536
8 : 32768
16 : 16384
32 : 8192
64 : 4096
128 : 2048
256 : 1024
512 : 512
The Highest Proper Divisor Is
--------
 131072 
--------
It took 0.09 seconds to finish finding the divisors.
----------------------------------
Do You Want Restart?

Answer 1

Here are some thoughts on this code:

Chose descriptive function names

The name programme is not really very descriptive of what the function does. You might call it something like factor to give the reader of your code a better idea of what it actually does.

Document your code

Python supports the use of multiple different kinds of comments, including ones that can be made into unit tests. Get in the habit of commenting your code carefully.

Separate I/O from calculation

The main purpose of the program is to factor numbers into divisors which is something that is potentially reusable. Both to make it more clear as to what the program is doing and to allow for future re-use, I'd suggest extracting the factoring part into a separate function and the have the input from the user be done within the main routine or some other input-only function.

Separate timing from the thing being timed

On my machine, the timer always reports 0.0 seconds, which makes it hard to compare the effects of changes in the code. For that reason, what's often done is to call the routine to be timed multiple times to get better resolution. In order to do that, you'd have to remove the timing from the routine you're timing, which is good design practice anyway. Right now, the print function is part of the code that's being timed.

Think of your user

Right now, the user has to enter "yes" or the equivalent and then enter another number to be factored. However, the prompt doesn't suggest that "y" is a valid answer. Adding that to the prompt would help the user understand what the computer is expecting. Better still, would be t eliminate that question and to simply ask for the next number with a number '0' being the user's way to specify no more numbers. Of course the prompt should be changed to tell the user of this fact.

Expand the range

Right now, the size of numbers that can be factored is limited to what will fit within an int, but it would be much more interesting to be able to factor really large numbers.

Use divmod() to save some time

Right now, for every successfully discovered divisor, the program performs three division operations: one for %, and then two more to insert the number into numbers and again to print. Instead, you could do the division once using the divmod function which gives you both the quotient and remainder at the same time.

Answer 2

First issue: This is a micro-optimization and therefore not necessarily a good idea.

I note that you say

while i <= math.sqrt(intnum):

which recomputes the square root every time. You could compute it once and store it. Alternatively you could say

while i * i <= intnum:

which is likely to be a cheaper and more accurate computation than finding the square root.

Second issue: Typo

except ValueError:
   error("NOT VALID NUMBER")
except OverflowError:
   error("NUMBER IS TO LARGE")
except:
   error("UNKNOWN ERROR")

STOP SHOUTING AT ME. Also you have a typo. It should be "TOO LARGE", not "TO LARGE".

Issue 3: Minor Bug

Try putting in a perfect square. The numbers list will contain two copies of the root. That is harmless in your program as it stands, but if your intention is to use that list for something else in the future, it seems bizarre that there should be a duplicate.

Issue 4: Minor performance issue

Why add the inverse divisors to the list in the first place? You could remove

       numbers.insert(0,int(intnum/i))

You know that numbers[0] is one, so you could simply say:

largestProper = 1 if len(numbers) = 1 else intnum/numbers[1]

Issue 5: Scalability issue

The performance is very poor if the number is very large; this is an extremely naive way to solve this problem.

A less naive way would be to compute a sequence of prime numbers, then test the number to see what prime numbers it is divisible by. Once you know the prime factorization of the number then the set of proper divisors is the set of all combinations of multiplications of the elements of the prime factorization.

To take a small example, suppose you are trying to find all the divisors of 120. Your technique is to loop from 1 to 11 trying out each possible divisor. Instead you could first say "120 is divisible by 2, leaving 60. 60 is divisible by 2 leaving 30. 30 is divisible by 2 leaving 15. 15 is divisible by 3 leaving 5. 5 is divisible by 5 leaving 1, we're done." Now you know that the factorization is 2x2x2x3x5. To find the largest proper divisor you replace the smallest number by 1 -- 1x2x2x3x5 is the largest proper divisor of 120.

To find all the divisors, you try all the combinations of 0, 1, 2 or 3 twos, 0 or 1 threes, 0 or 1 fives:

1x1x1x1x1 -- zero twos, zero threes, zero fives
1x1x2x1x1 -- one two, zero threes, zero fives
1x2x2x1x1 -- two twos, zero threes, zero fives
2x2x2x1x1 -- three twos, zero threes, zero fives
1x1x1x3x1 -- zero twos, one three, zero fives
1x1x2x3x1 -- one two, one three, zero fives
...

And so on.

This seems a lot more complicated -- and it is -- but this algorithm is far faster for really large numbers. If you were trying to factor a 20 digit number your system would have to try ten billion or more trial divisions.

Answer 3

I'm new, so can't comment, otherwise, would have commented. This isn't a bug, but you don't necessarily need the brackets in python for ifs and things like that: Instead of:

if (intnum % i) == 0:

you could just do:

if intnum % i == 0:

I know it might not be very helpful, but in some cases, I think it can help readability if you ever edit it again. I used to put brackets in coming from c# but it really could confuse you - I spent hours looking for an error because of the unessential brackets.

Answer 4

Here are a couple small things:

• Where you do

  print("----------------------------------")
  

  it might be easier to do print("-" * 34). I use this all the time with really long repeat elements. It also makes it easy to keep things the same length sometimes.

• Where you have

  print("The Highest Proper Divisor Is\n--------\n",str(numbers[1]) , ...
  

  it is really long, perhaps you could break it into multiple prints somewhat like this:

  print("-" * 34)
  print("ERROR - {}".format(error))
  print("-" * 34)