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

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?

-

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.

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.

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.

-
In Python 3, all numbers will fit in an int, assuming sufficient memory is available. In other words, int has unlimited precision. – codesparkle Apr 28 '14 at 0:17
@codesparkle: when I enter 38018301831 the program reports "ERROR - NUMBER IS TO LARGE" suggesting a range limitation. Can you explain what's happening? – Edward Apr 28 '14 at 0:31
That's because of numbers = array("i",[]). The OP should have used numbers = [] instead. So the restriction doesn't come from the use of the Python int, but from the use of the array with a type code of i which translates to a C long (which is not long enough to hold 38018301831). – codesparkle Apr 28 '14 at 2:02
@codesparkle: Ah, thanks for the explanation. After I modified the code to use a plain list, it factors even large numbers. – Edward Apr 28 '14 at 2:17
@codesparkle thanks for pointing out the array thingy...I didn't know that's how u made a list I though like many other languages it had to be formatted so I tried import array, it worked so guessed that was the way to do it! – Oliver Perring Apr 30 '14 at 14:56

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.

-
mmmm I don't quite understand how to do this...ive tried multiple times and failed again and again any pointers? – Oliver Perring Apr 30 '14 at 14:55
@OliverPerring: I am not a python programmer so I don't know what the pythonic way to do so is. Consider looking up "Cartesian Product"; the set of all divisors is related to the Cartesian Product of the factorization. – Eric Lippert Apr 30 '14 at 15:23
ok I will thank you – Oliver Perring Apr 30 '14 at 15:42

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.

-
ahh ok ive also come from c# programming @user41412 this is a realy helpful thing to point out. Do you know if this also works with things like print? and while? – Oliver Perring Apr 27 '14 at 14:09
@ Oliver Perring, Well, with Python 3, you obviously need the print('Hello World') brackets, with while loops, for the condition, you don't, so you could say while x != 2: instead of while (x != 2): In your case, while(running): needs only be while running: That's why I prefer Python to other languages - its relatively simple – ᔕᖺᘎᕊ Apr 27 '14 at 14:11
Hi, and welcome to Code Review. Here we welcome any answers that have valuable suggestions, even if they are small. This is a decent answer. – rolfl Apr 27 '14 at 14:50
Tips like this make code far harder to interpret for other programmers. Does it really take much more time to write if ((intnum % i) == 0):? – Joshpbarron Apr 28 '14 at 10:37

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)

-
Even simpler would be this: print("{0}\nERROR - {1}\n{0}\n".format("-"*34,format(error)) – Edward Apr 27 '14 at 16:53
@Edward I don't quite understand how your suggestion works! Can you please explain to me. Sorry for being a noob and all. – Oliver Perring Apr 28 '14 at 17:07
@OliverPerring: No problem. The format function uses a thing called a format specification which is a little like the C language printf if you're familiar with that. In my suggestion, {0} is a placeholder for the first argument (which is "-"*34 in this case) and {1} is for the second argument. The format string just uses {0} twice to print the two lines of - characters. – Edward Apr 28 '14 at 19:12
@Edward that makes sense I did use to use printf but not very well looks a little simpler in python will play around with it – Oliver Perring Apr 30 '14 at 14:53
Thnx ive now added this to my code along with a few extra selections...when i have time i will updatw the question and add in the changes – Oliver Perring May 3 '14 at 11:49