John Lekberg


JUNTO Practice - "Project Euler Problem 35"

Discussed on 2019-01-02.

Project Euler Problem 35


Solution - John

#!/usr/bin/env python3

"""Solution to Project Euler Problem 35 - Circular Primes."""

import numpy
import collections
import typing

__author__ = "John Lekberg"


def circular_primes_under(n: int) -> int:
    primes = primes_up_to(1_000_000)
    count = 0
    prime_set = set(primes)
    for p in prime_set:
        if all(r in prime_set for r in rotations(str(p))):
            count += 1
    return count


def rotations(s):
    for i in range(len(s)):
        yield int(s[i:] + s[:i])


def primes_up_to(n: int):
    """Primes for 2 up to n.
    See primesfrom2to at https://stackoverflow.com/questions/2068372.
    """
    assert n >= 6
    sieve = numpy.ones(n // 3 + (n % 6 == 2), dtype=numpy.bool)
    for i in range(1, int(n ** 0.5) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3 :: 2 * k] = False
            sieve[k * (k - 2 * (i & 1) + 4) // 3 :: 2 * k] = False
    return numpy.r_[
        2, 3, ((3 * numpy.nonzero(sieve)[0][1:] + 1) | 1)
    ]


print(circular_primes_under(1_000_000))

Solution - Oscar

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Dec 25 23:17:02 2018

@author: oscarmartinez
"""

import math as m


def hasDigit1(n):
    while n > 0:
        if n % 10 in {2, 4, 6, 8, 5, 0}:
            return False
            break
        n = n // 10
    return True


def sievePrime(maxN):
    primes = [True for i in range(maxN + 1)]
    p = 2
    while p * p <= maxN:
        if primes[p] == True:
            for i in range(p * 2, maxN + 1, p):
                primes[i] = False
        p += 1

    return {
        j for j in range(3, maxN, 2) if primes[j] and hasDigit1(j)
    }


def rot(n, base):
    l_b = 10 ** base
    return 10 * (n % (l_b)) + (n // l_b)


def getRots(n):
    base = m.floor(m.log10(n))
    rot_lst = []
    rot_lst.append(n)
    for _ in range(base):
        rot_lst.append(rot(rot_lst[len(rot_lst) - 1], base))
    return rot_lst[1:]


def CircularPrimes(n):
    c = False
    cnt = 0
    prime_set = sievePrime(n)
    prime_set.add(2)
    seen_set = set()
    for pr in prime_set:
        if pr in seen_set:
            continue
        seen_set.add(pr)
        rots = getRots(pr)
        for rp in rots:
            seen_set.add(rp)

            if not rp in prime_set:
                c = True
        if not c:
            cnt += len(rots) + 1
        else:
            c = False

    print(cnt)


CircularPrimes(1000000)