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
– deceze ♦, Commented May 9, 2017 at 0:35
Your problem is not specific to Python. You need to make the algorithm more efficient. Look into factoring algorithms. — phihag
– phihag, Commented May 9, 2017 at 0: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
– Paul Rooney, Commented May 9, 2017 at 0:48
@PaulRooney thank you i tried that and it took 4 seconds off — Moustafa Mohamed
– Moustafa Mohamed, Commented May 9, 2017 at 0:52

thomaskeefe · Accepted Answer · 2017-05-09 00:46:00Z

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 9, 2017 at 0:46

thomaskeefe

2,48223 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Moustafa Mohamed Over a year ago

for all the for loops or for the factors ones only?

Moustafa Mohamed Over a year ago

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

thomaskeefe Over a year ago

I would round the square root up to the nearest whole number using math.ceil

Stefan Pochmann · Accepted Answer · 2017-05-09 01:16:28Z

0

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).

answered May 9, 2017 at 1:16

Stefan Pochmann

29k9 gold badges48 silver badges117 bronze badges

Collectives™ on Stack Overflow

How to make my program more efficient in python?

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest