nekedome / project-euler

solutions/problem35.py

"""
Project Euler Problem 35: Circular Primes
=========================================

.. module:: solutions.problem35
   :synopsis: My solution to problem #35.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem35.py>`_.

Problem Statement
#################

The number, :math:`197`, is called a circular prime because all rotations of the digits: :math:`197, 971`, and

This line is too long as per the coding-style (110/100).

:math:`719`, are themselves prime.

There are thirteen such primes below :math:`100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79`, and :math:`97`.

This line is too long as per the coding-style (109/100).

How many circular primes are there below one million?

Solution Discussion
###################

Simply iterate over the primes below one million and count how many satisfy the conditions for a circular prime.

This line is too long as per the coding-style (112/100).

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem35.py
   :language: python
   :lines: 34-
"""

from typing import Iterator

from lib.digital import num_digits
from lib.sequence import Primes


def rotated(p: int) -> Iterator[int]:

The name p does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    """ Generate all rotations of the decimal digits of `p`

    :param p: the initial value of `p`
    :return: a generator of all decimal digit rotations of `p`
    """

    def rotl(x: int, n: int) -> int:

The name x does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name n does not conform to the argument naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

        """ Helper function to rotate the decimal digits of `x` left by one position

        :param x: the integer to rotate
        :param n: the number of decimal digits in `x`
        :return: x left rotated by one digit
        """

        return ((x * 10) + int(x // (10 ** (n - 1)))) % (10 ** n)

    n_digits = num_digits(p, base=10)
    q = rotl(p, n_digits)

The name q does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    while q != p:
        yield q
        q = rotl(q, n_digits)

The name q does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

def solve():
    """ Compute the answer to Project Euler's problem #35 """

    upper_bound = 1000000

    # Get all primes lower than one million, build a set to make membership tests cheap, i.e. O(1)
    primes = set(Primes(upper_bound=upper_bound))

    # Iterate over the primes, checking for those that are circular
    answer = 0
    for prime in primes:
        for q in rotated(prime):

The name q does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

            if q not in primes:
                break
        else:
            answer += 1

    return answer


expected_answer = 55

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).