Hey everyone! I am working on a Perfect Number Calculator, and I recently got it working! I was wondering if anyone knew an easy, sure-fire way to make computations faster. For my calculator, it basically checks all the factors, and if added together at the end, they will be the number (a perfect number). I have put the code below, does anyone know how to speed it up?

when green flag clicked
ask [Num?] and wait
NthPerfectNum (answer)
say (number) for (2) secs


define IsPerfect (num)
set [perfect? v] to [0]
set [i v] to [0]
set [sum v] to [0]
repeat ((num) - (1))
change [i v] by (1)
if <((num) mod (i)) = [0]> then
change [sum v] by (i)
end
end
if <(sum) = (num)> then
set [perfect? v] to [1]
stop [this script v]
end
stop [this script v]


define NthPerfectNum (num)
set [count v] to (0)
set [number v] to (1)
repeat until <not <(count) < (num)>>
change [number v] by (1)
IsPerfect (number)
if <(perfect?) = [1]> then
change [count v] by (1)
end
end

EDITS: Fixed Scratchblocks

Did you make sure to check the “run without screen refresh” setting for your custom blocks? Without that option, Scratch will pause at the end of your loop and run a little bit slower. It might also lag if the scripts take too long though…

I did enable it. While it did speed it up a small bit, it also lagged it out so much that it took 10 seconds for the “Stop” button to register…

Scratch is really slow, and the thing you’re doing involves a lot of computation so it’s bound to take a long time. Try running it in turbowarp and/or optimizing the algorithm to do less computation.

I don't think the code can be made much faster without improving the algorithm. The simplest way to optimize it is to only check divisors less than equal to the square root of num. If num is divisible by i, you then add both i and num/i to the sum (unless i = num/i).

This probably still isn't optimal – I believe using a variant of the sieve of Eratosthenes to compute the prime factorization of all numbers and then using that to find the divisors would be even more efficient.

That… is way more than my useless calculator brain can understand. Could you put that in simpler terms? If not that's fine, I'm just not 100% sure I know what you mean lol

wombat2lps wrote:

That… is way more than my useless calculator brain can understand. Could you put that in simpler terms? If not that's fine, I'm just not 100% sure I know what you mean lol

Divisors come in pairs – if a number n is divisible by d, it's also divisible by n/d. For example, if n is 24, the pairs will be:

• 2, 12
  
• 3, 8
  
• 4, 6
  

The first number of each pair can't be greater than the square root of n. So instead of checking for every number from 1 to n if it's a divisor, you can do something like this:

set [i v] to (1)
repeat until <(i) > ([sqrt v] of (num))>
if <((num) mod (i)) = [0]> then
change [sum v] by (i)
if <not <(i) = ((num) / (i))>> then
change [sum v] by ((num) / (i))
end
end
end