Python 'for' loop is memory inefficient

Mark Lawrence breamoreboy at
Sat Aug 15 03:38:18 CEST 2009

Dr. Phillip M. Feldman wrote:
> I wrote the following correct but inefficient test of primality for purposes
> of demonstrating that the simplest algorithm is often not the most
> efficient.  But, when I try to run the following code with a value of n that
> is large enough to produce a significant amount of running time, I get an
> out-of-memory error!
> def is_prime(n):
>    for j in range(2,n):
>       if (n % j) == 0: return False
>    return True
> It seems as though Python is actually expanding range(2,n) into a list of
> numbers, even though this is incredibly wasteful of memory. There should be
> a looping mechanism that generates the index variable values incrementally
> as they are needed.
I have a strong suspicion that you will find hints in the Python 
documentation that this has already been addressed.  Perhaps you could 
try reading before posting?

Kindest regards.

Mark Lawrence.

More information about the Python-list mailing list