# Refactoring in 2 Dimensions

Recently on SO, I stumbled over the algorithm below:

for n in range(2, i):
for x in range(2, n):
if not (n % x):
break
print("{0} is PRIME".format(n))

The algorithm tests whether a number is a prime number or not. We commonly see nested `for` loops like this, but (for me) it is a very in-elegant style. Conceptually, we would ‘think’ or ‘speak’ this process by saying:

for each column in row:
do something

PROBLEM:    there is a disconnection between the ‘thought’ to the code. So it got me thinking, how can I refactor this to more closely resemble the ‘thought’?

SOLUTION 1:

Remove the `do something` into a separate function:

def is_prime(n):
for x in range(2, n):
if not (n % x):
return
print("{0} is PRIME".format(n))
return

numbers = (n for n in range(2, n))
for n in numbers:
is_prime(n)

Advantages:    Abstracting out the logic here is key! By removing the testing logic, we have a simple statement:

for each number --> test it

I like this, I think it accurately reflects the ‘thought’. But… we are still running two `for` loops, which I would like to avoid.

SOLUTION 2:

So my next thought was to use recursion:

def is_prime(n):
# base case
if n < 2:
return
else:
for I in range(2, n):
if not (n % i):
return is_prime(n – 1)
print(“{0} is PRIME”.format(n))
return is_prime(n -1)

Advantage:    we all love recursion! To me, this is a far more elegant solution – in the ‘programming’ sense. It is academically pleasant. When I read this, I don’t have to balance a 2-dimensional problem in my head, (for me) it is easier to comprehend.

Disadvantage:    It is disconnected from the thought once again. But I do prefer it to the original algorithm.

SOLUTION 3:

I have one more idea – is it possible to pass the output from one function, as the input to a second function? Something along the lines of:

is_prime( number([testset]) )

Using this idea, can we pass each number in the testset to is_prime() for evaluation? I haven’t got my head around how to implement this – anyone’s thoughts / ideas would be much appreciated!

I think python will also have a list comprehension or a generator solution for this as well, which I should further investigate.

— UPDATE

SOLUTION 4:

A Pythonic generator statement (note it uses the previously defined function, is_prime())

for prime in (n for n in testset if is_prime(n)): print("{} is PRIME".format(prime))

Nicely Pythonic – and reasonably close to the `thought`