Проект Эйлера # 35 - Круговые Штрихи

Question

Я пытаюсь решить Project Euler's problem #35, который спрашивает:

число, 197, называется круговой простой, потому что все повороты цифры: 197, 971 и 719, сами по себе простые.

Есть тринадцать таких простых чисел ниже 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 и 97.

Сколько круговую простых чисел есть ниже один миллион?

Для того, чтобы решить эту проблему, я использую следующий код в Swift:

let size = 1000000 

func ESieve(x : Int) -> [Bool] { 

    var primes = [Bool](count: x + 1, repeatedValue: true) 
    primes[0] = false 
    primes[1] = false 

    for var i = 2; i < primes.count; i++ { 
     if !primes[i] { 
      continue 
     } 

     for (var j = 2*i; j < primes.count; j += i) { 
      primes[j] = false 
     } 
    } 

    return primes 
} 

let sieve = ESieve(size) 

func getPrimes() -> [Int] { 

    var array = [Int]() 
    for (var i = 0; i < sieve.count; i++) { 
     if sieve[i] { 
     array.append(i) 
     } 
    } 
    return array 
} 

let primes = getPrimes() 


func rotations(v : [Int]) -> [Int] { 
    var result = [Int]() 

    for (var i = 0; i < v.count; i++) { 
     var r = 0 
     for (var j = i; j < v.count + i; j++) { 
     r = 10*r + v[j % v.count] 
     } 
     result.append(r) 
    } 
    return result 
} 

func getArray(x : Int) -> [Int] { 

    var array = [Int]() 
    var i = x 
    while i > 0 { 
    array.append(i%10) 
    i /= 10 
    } 
    return array 
} 

func isAllPrime(v : [Int]) -> Bool { 

    for i in v { 
    if !sieve[i] { 
     return false 
    } 
    } 
    return true 
} 

var s = 0 
for (var i = 0; i < primes.count; i++) { 
    var array = getArray(primes[i]) 
    var perms = rotations(array) 
    if isAllPrime(perms) { 
     s++ 
    } 
} 

println(s) 

Все функции работают должным образом. Даже когда я установил size в 100, я получаю правильный результат 13 с правильными круговыми числами, но я все время получаю неправильный результат и не вижу, где проблема.

Answer 1

Я не хочу лишать вас радости нахождения раствора РЕ, поэтому я дам только намек:

Проверьте выход rotations(getArray(N)) для чисел N с 3 или более цифр. Это не то, что вы ожидаете (но может быть легко исправлено).

Answer 2

Я думал, что Мартин указывает на проблему с его ответом, тем не менее, я думаю, что в такой проблеме эффективность тоже очень важна.

Мой совет, чтобы улучшить свой код в вашем решета Эратосфена, вы можете улучшить его много изменив следующую строку:

for i in 2..<primes.count 

Для этого:

for (var i = 2; i * i <= primes.count; ++i) 

выше улучшение выполнения только простое просеивание, не превышающее корень n.

Есть больше улучшений вы можете сделать это, но зависят от вас, я настоятельно рекомендую вам следующие две статей опытного русского кодера в конкурсе программирования:

• Sieve of Eratosthenes
• Sieve of Eratosthenes with linear time work

Вы должны перевести его, чтобы прочитать его, потому что на русском языке, но вы можете использовать переводчик Google.

Я надеюсь, что это поможет вам.

Answer 3

Подсказка. Подумайте, что произойдет, если ваш начальный штрих, перед вращением, содержит цифру «8».