find all multiplicands and multipliers for a number

Marko Rauhamaa marko at
Sat Apr 11 19:31:32 CEST 2015

Paul Rubin < at nospam.invalid>:

> Marko Rauhamaa <marko at> writes:
>> This is slightly faster:...
>> def fac(n):
>>     for c in range(n):
>>         if c*c > n: ...
> That's interesting and says something bad about generators in Python
> 3. It's doing 3 times as many trial divisions as the version I posted,
> and it's still faster?

I think it mostly says divisions are not so evil as you think they might
be. Also, I wouldn't bother optimizing Python's performance too much.
Python is very wasteful wrt space and speed -- and for good reasons.
Either Python does it for you or it doesn't. If it doesn't, write that
part in C.

Myself, I write in bash what I can. What I can't, I write in Python.
What I can't write in Python, I write in C.


PS Note that you're being "wasteful" by multiplying c*c over and over
again instead of calculating the square root of n a handful of times.
But since multiplication isn't all that expensive, the square root
optimization doesn't affect execution time measurably.

More information about the Python-list mailing list