Skip to content

Instantly share code, notes, and snippets.

@mluisbrown
Created July 10, 2016 11:58
Show Gist options
  • Save mluisbrown/a662ea4edb4228e50e81249a1e130992 to your computer and use it in GitHub Desktop.
Save mluisbrown/a662ea4edb4228e50e81249a1e130992 to your computer and use it in GitHub Desktop.
Swift code to find and count all Circular Primes below 1 million (Project Euler problem 35)
// Circular primes
// Problem 35
// The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
//
// There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
//
// How many circular primes are there below one million?
import Foundation
struct ESieve {
let primes: Set<Int>
init(size: Int) {
let sieve = ESieve.populateSieve(ofSize: size)
primes = Set(ESieve.primes(fromSieve: sieve))
}
static func populateSieve(ofSize size: Int) -> [Bool] {
var sieve = Array<Bool>(count: size, repeatedValue: true)
let endIndex = Int(ceil(sqrt(Double(size))))
for i in 0...1 {
sieve[i] = false
}
for i in 2...endIndex {
if sieve[i] {
let startIndex = Int(pow(Double(i), 2.0))
startIndex.stride(to: size, by: i).forEach {
sieve[$0] = false
}
}
}
return sieve
}
static func primes(fromSieve sieve: [Bool]) -> [Int] {
var primes = [Int?]()
for n in sieve.indices {
primes.append(sieve[n] ? n : nil)
}
return primes.flatMap { $0 }
}
func isPrime(n: Int) -> Bool {
return primes.contains(n)
}
}
func getRotations(ofNumber number: Int) -> [Int] {
var rotations = [Int]()
let exponent = Int(floor(log10(Double(number))))
guard exponent > 0 else {
return rotations
}
let multiplier = Int(pow(10, Double(exponent)))
var rotation = number
for _ in 1...exponent {
let units = rotation % 10
let shifted = rotation / 10
rotation = units * multiplier + shifted
rotations.append(rotation)
}
return rotations
}
func circularPrimes(below size: Int) -> [Int] {
let sieve = ESieve(size: size)
var circulars = Set<Int>()
for prime in sieve.primes where !circulars.contains(prime) {
let rotations = Set(getRotations(ofNumber: prime))
if rotations.count == 0 {
circulars.insert(prime)
continue
}
if rotations.isSubsetOf(sieve.primes) {
circulars.unionInPlace(rotations)
circulars.insert(prime)
}
}
return circulars.sort()
}
let size = 1000000
let foo = circularPrimes(below: size)
print("Number of circular primes below \(size): \(foo.count)")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment