Ruby Project Euler 35-Circular Primes錯誤的答案

Question

我在Ruby嘗試了Project Euler question 35（我對它很陌生）並且得到了錯誤的答案。

問題：

的數量，197，被稱爲圓形素，因爲 數字所有旋轉：197，971，719，本身就是黃金。

有低於100 13米這樣的素數：2，3，5，7，11，13，17，31，37 ，71，73，79，和97。

多少圓形的素數是有低於一百萬？

我的代碼：

require 'prime' 

def primes(n) 
    nums = [nil, nil, *2..n] 
    (2..Math.sqrt(n)).each do |i| 
    (i**2..n).step(i) { |m| nums[m] = nil } if nums[i] 
    end 
    nums.compact 
end 

prime = primes(1000000)  
circularPrimes = 0 

prime.each do |j| 
    puts "\n" 
    puts j 
    flag = false 
    j = j.to_s() 
    for k in (0..j.length) 
    temp = j[k..-1] + j[0..k] 
    temp = temp.to_i() 
    a = Prime.prime?(temp) 
    if a == false then 
     flag = true 
     break 
    end 
    end 

    if flag == false then 
    circularPrimes += 1 
    end 
end 

puts"\n\n\n\n\n" 

puts circularPrimes 

我想不出在代碼中的問題（我認爲這是罰款）。

Answer 1

您正在重新發明了兩兩件事：

• 生成素數高達N（使用Prime.each(n)）
• 旋轉的數字（使用Array#rotate!）

也許問題出在那裏的地方。我會做這種方式：

require 'prime' 

def rotations(x) 
    digits = x.to_s.chars 
    digits.map do 
    digits.rotate!.join.to_i 
    end 
end 

circular_primes = Prime.each(1_000_000).select do |p| 
    rotations(p).all?{|r| Prime.prime?(r) } 
end 

puts circular_primes.count 

Answer 2

我覺得你的旋轉是關閉的1，試圖

j="123456" 
j[1..-1] + j[0..1] # that is k=1 from the above code 

產生

"2345612" 

這不會是一個旋轉。可以通過

temp = j[k..-1] + j[0...k] 

Answer 3

正如Patru提到的，你的輪換是不正確的。我也不確定你的primes方法，但我沒有嘗試解決它。既然你不反對使用Prime這個類，我反而用它來解決眼睛上的問題，並且據我所知可以更正確。雖然它表現得相當糟糕，但也許它可以被優化。它會返回1_000_000的答案，但大概需要70秒，看起來非常長。

我想我不應該經歷所有的數字，我應該至少跳過我已經處理和確定的所有旋轉都是圓形的素數或不是。無論如何，現在你需要做一些優化。

require 'prime' 

def circular_prime?(n) 
    rotations(n).all? { |r| Prime.prime? r } 
end 

def rotations(n) 
    str = n.to_s 
    (0...str.length).map do |i| 
    (str[i..-1] + str[0...i]).to_i 
    end 
end 

(2 .. 100).select { |n| circular_prime?(n) } 
# => [2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97] 

結合你primes方法，可以將圓形黃金一代改變

primes(1_000_000).select { |prime| circular_prime? prime } 

的行爲等同於你的代碼，它首先選擇所有素數達一百萬，然後選擇圓從那裏開始。稍微優化就是從旋轉中刪除原始數字進行檢查，因爲我們已經知道它是素數。

對於這個變體，我確實獲得了50秒的單一時間，所以這至少看起來比我原來的（〜70秒）快，這並不奇怪，因爲我經歷了所有數字在2到100萬之間的所有旋轉，而通過首先選擇質數，輸入到rotations的輸入顯着減少。