项目欧拉#35 - 圆形素数

Question

我正在尝试解决Project Euler的问题#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

我不想剥夺您找到PE解决方案的乐趣,因此我只给出一个提示:

检查的输出rotations(getArray(N))为数字N有3个或多个数字.这不是你所期望的(但可以很容易地修复).