1
\$\begingroup\$

I solved problem 58 in Project Euler and I am happy with my solution. However, are there any areas where I can improve my code here as I am learning how to write good python code.

Prompt:

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

#! /usr/bin/env python

from funcs import isPrime


# Corner values of a square of size s have values:
# s^2 - 3s + 3, s^2 - 2s + 2, s^2 - s + 1, s^2


def corner_values(n):
    """
    returns a tuple of all 4 corners of an nxn square

    >>> corner_values(3)
    (3, 5, 7, 9)
    """
    return (n ** 2 - 3 * n + 3, n ** 2 - 2 * n + 2, n ** 2 - n + 1, n ** 2)


def main():
    ratio, side_length = 1, 1
    primes, total = 0, 0
    while ratio >= 0.1:
        side_length += 2
        for n in corner_values(side_length):
            if isPrime(n):
                primes += 1
                total += 1
            else:
                total += 1
        ratio = primes / total
    return side_length - 2


if __name__ == "__main__":
    print(main())
\$\endgroup\$
2
  • \$\begingroup\$ What is funcs module? \$\endgroup\$ Jul 20, 2021 at 8:16
  • \$\begingroup\$ @PavloSlavynskyy These are some local helper functions I have written. \$\endgroup\$
    – SSSNIPD
    Jul 20, 2021 at 9:57

1 Answer 1

2
\$\begingroup\$

Identifiers consistency

PEP8 recommends snake_case, not camelCase for functions and variables; isPrime breaks this. Moreover, PEP8 recommends consistency over other matters (except for readability). If it's your function - maybe you should rework it one way or another?

main is unclear name

Yes, it makes clear that it makes some "main work" in the file, but find_prime_diagonals_size (ok, bad example) or something like that could be more readable. How about solve_euler58?

DRY in if branches

If the last statement in both if and else branches is the same - it can be moved out and put after if-else:

        if isPrime(n):
            primes += 1
        total += 1

The same applies if you have first statement the same - it could be put before if.

total and side_length are loop variables and are defined by each other

total increases by 4 every while iteration, and side_length increases by 2. Consider using only 1 variable and (arguably) itertools.count, like

for side_length in itertools.count():
    ...
    if primes/(side_length*2-1)<0.1:
        return side_length

corner_values return a progression, so it can be replaced with range

range(n**2 - 3*n + 3, n**2 + 1, n - 1)

returns the same values as corner_values, even probably slightly faster, but I'm not sure if it's more readable. Probably not. Still, you should be aware of possibilities.

Divisions are slower than multiplications, floating point operations are slower than integers

It's not really important here; but I think you should know that. You're calculating primes / total >= 0.1 every loop; multiply both sides by 10*total, and the expression will be 10 * primes >= total, which calculates slightly faster. I don't think it's really needed here, it looks more readable in the first form, just FYI.

Complexity of isPrime is unknown

I think this is the bottleneck of the code. Does it use any sieve or is just a brute force division check?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.