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)
seen_set = set()
for pr in prime_set:
if pr in seen_set:
continue
rots = getRots(pr)
for rp in rots: