My Code for Perfect Number

Question

So far, I've learned about for loops, if statements, and counting so it would be great to get feedback using only these topics. I was trying to solve the Perfect Number problem where the divisors excluding the number add up to that number. So for 6, The divisors 1,2,3 add up to 6. I've tried looking at other posts, but I wanted to know why my code specifically isn't working. I've tried solving the problem, and I feel that I'm almost there. I just have one issue. This is what I have so far:

#

num = 30

for i in range(1,num+1):
    count = 0
    for k in range(1,num+1):
        if i%k == 0 and i!=k:
            count += k
            if count == i:
                print(k,'Perfect',i)

#

The output on shell gives me this:

3 Perfect 6
8 Perfect 24
14 Perfect 28

#

I know that 24 is not a perfect number. The highest divisor for 24 excluding 24 should be 12, but I'm getting 8. This is why it's showing me that 24 is perfect. Can anyone clarify why I'm not able to get 12?

That's because when `k` is 8, count is 16, and so 16+8 is 24, which passes your `count == i` check. You skip any further divisors. — Burhan Khalid, Jul 29 '18 at 04:57
If you're satisfied with any of the answers, you should [accept one](https://stackoverflow.com/help/someone-answers). — Graham, Jul 29 '18 at 05:08

lenik · Accepted Answer · 2018-07-29T05:02:50.993

2

You have to count all divisors, before you make a conclusion, your code goes up to 8 for 24, then sums up all divisors so far and declares 24 a perfect number, not waiting for other divisors to appear.

Your code should looks like this:

for i in range(1,num+1):
    count = 0
    for k in range(1,i):  # no point searching for numbers greater than i
        if i%k == 0 :
            count += k
    if count == i:
        print('Perfect',i)

and produce:

('Perfect', 6)
('Perfect', 28)

edited Jul 29 '18 at 05:02

answered Jul 29 '18 at 04:57

lenik

23,228
4
34
43

The same answer with you. – Charles Cao Jul 29 '18 at 06:18
@CharlesCao thank you, you may upvote instead of commenting =) – lenik Jul 29 '18 at 06:23

Graham · Answer 2 · 2018-07-29T16:19:21.463

1

Your problem is that you're checking whether count == i in the wrong place. You need to check after the entire count summation is finished, not after each addition to the count sum.

num = 30

for i in range(1,num+1):
    count = 0
    for k in range(1,num+1):
        if i%k == 0 and i != k:
            count += k
    if count == i:
         print(k,'Perfect',i)

Also, if you want slightly more efficient code, you could do the subtraction afterwards instead of checking each value. Also, as lenik suggested, you only need to count to i (since i can't have any divisors larger than itself.) Even more efficiently, one could just use a Sieve of Eratosthenes-like approach, and count to sqrt(i)+1, finding the corresponding factors along the way:

from math import sqrt    

num = 30

for i in range(1,num+1):
    count = 0
    for k in range(1,sqrt(i) + 1):
        if i%k == 0:
            count += k
            factor = count/k
            # The conditional is necessary in case i is a perfect square.
            if k != factor:
                count += factor
    if count - i == i:
         print(k,'Perfect',i)

edited Jul 29 '18 at 16:19

answered Jul 29 '18 at 04:58

Graham

3,153
3
16
31

1

if you want to be efficient, replace `for k in range(1, num+1)` with `for k in range(1, i)`, because there's no point searching for numbers greater than `i`. – lenik Jul 29 '18 at 05:01
Good suggestion. There's probably overall a more efficient implementation anyway, but it's always good to be able to improve. – Graham Jul 29 '18 at 05:08
you may improve even more, iterating upto `(i+1)/2`, because there will be no divisors above that =) – lenik Jul 29 '18 at 06:24
@lenik Better yet, I could use `sqrt(i) + 1` and find the corresponding divisor. That's the absolutely optimal method for this method. But there are [even better ways](https://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number) of doing it. – Graham Jul 29 '18 at 15:53

score 0 · Answer 3 · edited Sep 16 '19 at 07:26

0

12 is not perfect 1 + 2 + 3+ 4 + 6 != 12 second for also have problem in count (change it to i+1) and critical problem was las check was in for

num = 30

for i in range(1,num+1):
    count = 0
    last = 0
    for k in range(1,i):
        if i%k == 0:
            count += k
            last = k
    if count == i:
        print(last,'Perfect',i)

result :

3 Perfect 6

14 Perfect 28

edited Sep 16 '19 at 07:26

Martin Thoma

124,992
159
614
958

answered Jul 29 '18 at 05:01

Nozar Safari

505
4
17

1

There are no possible `i==k`, so the `i != k` could be removed – Charles Cao Jul 29 '18 at 06:17

My Code for Perfect Number

#

#

#

3 Answers3