How to make my program more efficient in python?

Question

So my task is this: A number, n, is called lean if the sum of all its factors is n + 1. A number, n, is called fat if the sum of all its factors is greater than 3*n. A number, n, is called Jack Sprat if it is both lean and the next number, n + 1 is fat.

I have to ask the user to input a number and I have to say whether it is lean, fat or Jack Sprat. I also have to print all the numbers that are jack sprat from 1 to 10000 in 1 second.

This program takes about 10 seconds to do that

Here is the Code:

def isLean(n, t):
if t == n + 1:
    return True
else:
    return False

def isFat(n, t):
    if t > 3*num:
        return True
    else:
        return False

def isJackSprat(n, t, t2):
    if t == n+1 and t2 > 3*(n+1):
        return True
    else:
        return False

num = int(input("Please enter a number: "))

total = 0
total2 = 0
total3 = 0
total4 = 0
prime = ""

for factor in range(1,num+1):
    if num % factor == 0:
        total += factor

for factor in range(1,num+2):
    if (num+1) % factor == 0:
        total2 += factor

if isLean(num,total) == True:
    print ("Lean: Yes")
elif isLean(num,total) == False:
    print ("Lean: No")

if isFat(num,total) == True:
    print ("Fat: Yes")
elif isFat(num,total) == False:
    print ("Fat: No")

if isJackSprat(num, total, total2) == True:
    print ("Jack Sprat: Yes")
elif isJackSprat(num, total, total2) == False:
    print ("Jack Sprat: No")


print ("These are the Jack Sprat Numbers from 1 - 1000")

for count in range (1,10000):
    if count % 2 != 0:
        for factor in range (1,count+ 1):
            if factor %  2 != 0:
                if count % factor == 0:
                    total3 += factor
        for factor in range (1,count+2):
            if (count+1) % factor == 0:
                total4 += factor 
        if total3 == (count + 1) and total4 > 3*(count + 1):
            prime = prime + str(count) + ", "
        total3 = 0
        total4 = 0

print (prime[0:len(prime)-2])

I would really appreciate it if I can get some help

Not efficiency, but style: whenever you have `if ...: return True else: return False`, just do `return ...`. The condition itself already evaluates to a boolean. — deceze, May 09 '17 at 00:35
Your problem is not specific to Python. You need to make the *algorithm* more efficient. Look into [factoring algorithms](http://stackoverflow.com/q/16007204/35070). — phihag, May 09 '17 at 00:43
one thought. Anywhere you do `if count % 2 != 0:`, you have unnecessary looping going on. Perhaps it would be better to limit your range to every second value? So the range call becomes `range(1, 100, 2)`. I don't think it will help you as much as an algorithmic alteration, but is useful as a step in learning. — Paul Rooney, May 09 '17 at 00:48
@PaulRooney thank you i tried that and it took 4 seconds off — Moustafa Mohamed, May 09 '17 at 00:52
How large can the input number be and how efficient must you be for that? — Stefan Pochmann, May 09 '17 at 00:58
@StefanPochmann It can be as large as you want but the efficiency for that part is almost instantaneous. The problem is in printing the JackSprat numbers — Moustafa Mohamed, May 09 '17 at 01:02
@MoustafaMohamed Instantaneous?! I just tried 573428957683402573095634705 and stopped it after it was still not done after a minute. — Stefan Pochmann, May 09 '17 at 01:10
@StefanPochmann oh, I didn't try any number that is as big as that. The efficiency part is only for printing the jack sprat numbers — Moustafa Mohamed, May 09 '17 at 01:28
Also `prime = prime + str(count) + ", "` is bad. Don't build up a string. It's inefficient as it involves temporaries. Instead build up a list and `join` it into a string at the point you print it. btw this question is pretty much unanswerable, it's too broadly scoped. You should read about [how to ask](https://stackoverflow.com/help/how-to-ask) a good question. I guess as you are young and no one wants to curb your enthusiasm, it's ok this one time :) You should also check out the [codereview](https://codereview.stackexchange.com/) stackexchange site. — Paul Rooney, May 09 '17 at 02:00

score 2 · Answer 1 · answered May 09 '17 at 00:46

2

You can get a big speed up by having your for loops only go up to the square root of the number. Each factor less than the square root will have a pair that is larger than the square root, so you can find all the factors by only iterating up to the square root.

answered May 09 '17 at 00:46

thomaskeefe

1,900
18
19

for all the for loops or for the factors ones only? – Moustafa Mohamed May 09 '17 at 00:53
it gives me an error because sometimes the square root of a number is a float, not an integer. I tried casting it to integer but then there was no output – Moustafa Mohamed May 09 '17 at 00:59
I would round the square root up to the nearest whole number using `math.ceil` – thomaskeefe May 11 '17 at 17:52

score 0 · Answer 2 · answered May 09 '17 at 01:16

Try it like the Sieve of Eratosthenes, but instead of a Boolean array and crossing out, have an int array which for each index builds up the sum of its factors. I just did that and it takes about 0.05 seconds to find all Jack Sprat numbers up to 10000 (the same that your code finds).

How to make my program more efficient in python?

2 Answers2