爲什麼我的ruby編碼找不到素數？

Question

我想知道爲什麼我的代碼不起作用。我對代碼世界很陌生，所以如果任何人都可以爲我解決這個問題，那麼最好的解決辦法是謝謝！

我想創建一個程序，它會指出我指定的數字列表中的素數。

請告訴我爲什麼這兩個代碼不起作用！我對第二個代碼試圖做什麼感到困惑，因爲我發現它是別人解決我的問題的方法。我是新來的編碼，但我喜歡它，所以忍受着我！

這裏是我的簡單的代碼：

def is_prime?(*nums) 

    i = 2 
    nums.each do |num| 
     while i < num 
      if num % i == 0 
       puts "#{num} is not a prime" 
      else 
       puts "#{num} is a prime" 
      end 
      i += 1 
     end 
    end 
end 

....爲什麼這不是工作？我怎樣才能使它工作？它不斷給我一個奇怪的答案，因爲它卡住我的第一號，似乎沒有處理下一個數字我插入，當我把：

puts is_prime?(21, 23, 17) 

這裏是我不是能夠要麼正確運行第二個代碼。有人可以打破這裏發生的事情嗎？我怎樣才能使它工作？

def is_prime?(*nums) 
    nums.each_with_object({}) do |num, hsh| 
     hsh[num] = num > 1 && 2.upto(num - 1).none? {|i| num % i == 0} 
    end 
end 

puts is_prime?(27, 13, 42) 

不管怎樣，我知道這個問題有點令人困惑，但如果有人在意輸入他們的2美分，我將不勝感激！哦，最後如何正確地在問題板上發佈代碼？如果沒有導師，我是如此的新鮮和困惑！

Answer 1

你有幾個問題。之前已經確定了一個：聲明i = 2的位置。這是你修正的代碼。

def is_prime?(*nums) 
    nums.each do |num| 
    i = 2 
     while i < num 
     if num % i == 0 
      puts "#{num} is not a prime" 
     else 
      puts "#{num} is a prime" 
     end 
     i += 1 
     end 
    end 
end 

當num % i == 0你所確定的數量不是素數，並打印一個消息到效果，但你繼續檢查，看它是否是整除比num減去所有較大的數字。每次你打印出來的數據都不是素數。問題是，一旦你確定一個數字不是素數，你就不需要繼續檢查。

另一個問題是，無論何時您打印的數字是質數num % i != 0。然而，這還爲時過早。除非您確定所有小於num的整數爲num % i != 0，否則無法得出結論。

讓我們看看如何解決這些問題。我認爲最簡單的方法是編寫一個單獨的方法來確定單個數字是否爲素數。我已經調用了該方法is_prime?並將其重命名爲主方法is_each_prime?。創建一個單獨的方法is_prime?的

def is_each_prime?(*nums) 
    nums.each { |num| 
    puts "#{num} is #{ is_prime?(num) ? '' : "not " }a prime" } 
end 

def is_prime?(num) 
    !(2...Math.sqrt(num)).any? { |i| num % i == 0 } 
end 

puts is_each_prime?(21, 23, 17) 
    #=> 21 is not a prime 
    # 23 is a prime 
    # 17 is a prime 

一個好處是，你可以單獨測試，以確保其工作正常。

Answer 2

您在循環之外初始化了i，因此後面的數字從i開始已經設置爲較高的值。

Answer 3

素數不包括evens（當然除外2），所以你可以在外部和內部循環中跳過它們。一旦你發現數字是素數，打破循環。這兩種技術大大加快了算法的速度，我的實驗是從10000秒陣列的3.9秒下降0.2秒。

標準inneficient算法首先：

class PrimeNumbers 

    def initialize(size) 
    @array = (2..size).to_a 
    @prime = [] 
    raise ArgumentError if size < 2 
    end 

    def process 
    @array.each do |i| 
     @prime.push(i) if inner_loop(i) 
    end 
    @prime 
    end 

    private 

    def inner_loop(e) 
    is_prime = true 
    e.downto(2) do |k| 
     next if k == e 
     if e % k == 0 
     is_prime = false 
     break 
     end 
    end 
    is_prime 
    end 

end 

下一步要問這些問題：

1. 哪裏跳過偶數？
2. 爲什麼甚至遍歷偶數？
3. 爲什麼要迭代超過某個點？
4. 一旦你傳遞數組的一半，有沒有機會擁有素數？

讓我們看看30X更快的算法（輸入50000大小，花了3秒，而不是98sec比較第一算法版本）：

class PrimeNumbers 

    def initialize(size) 
    raise ArgumentError if size < 2 

    @array = 1.step(size,2).to_a 
    @array.shift 
    @prime = [2] 
    end 

    def process 
    @array.each do |i| 
     @prime.push(i) if inner_loop(i) 
    end 
    @prime 
    end 

    private 

    def inner_loop(e, is_prime = true) 
    3.step(e/3, 2) do |k| 
     if e % k == 0 
     is_prime = false 
     break 
     end 
    end 
    is_prime 
    end 

end 

取決於算法的效率時的結果可以如下（原數組50000尺寸）：

96.824695s (loop through all array) 
92.385227s (loop through all array, skip even numbers in inner loop) 
9.251714s (loop through all array, skip even numbers in outer loop) 
5.901579s (loop through outer loop odds only) 
3.480197s (loop through outer loop odds only, cut half) 
2.329469s (loop through outer loop odds only, cut two thirds) 

爲什麼要減半？因爲67/51不能是整數。爲什麼要減少第三？有很強的依賴性。看看分隔符爲單號：

UPDATE：

潛水深入算法我發現，通過半或初始陣列的甚至第三尺寸無需循環。最後，您可以迭代少於10％的數組來拒絕合成數字。

它相當容易削減1/2或1/3，但削減4/5你必須排除9，削減7/8 - 9,15,25等。它有助於循環通過只有小數據集忽略數組的其餘部分。參見下圖的詳細信息：

0.398072s (loop through odds only, cut selective block depend on initial size) 

什麼選擇性阻斷是什麼？讓我們選擇數組大小，例如8000和識破變量：

size   = 8000 
@loop_end  = 19 
@denominators = [9, 15, 21, 27, 33, 39, 45, 51, 25, 35, 45, 55, 65, 75, 85, 49, 63, 77, 91, 105, 119, 81, 99, 117, 135, 153, 121, 143, 165, 187, 169, 195, 221, 225, 255, 289] 

值的最大數量，你需要遍歷爲5％（19/20）！因此，爲了比較給定的值，不需要循環超過5-10％的值。

對於算法來說，循環421個元素來選擇素數就足夠了。如果輸入較大，@loop_end將適應。在較小的數據集（1000個值）上，變量爲：

size   = 1000 
@loop_end  = 9 
@denominators = [9, 15, 21, 25, 35, 49] 

循環遍歷111個元素有助於從1000個元素數組中找出素數。雖然@ denominators數組大於實際分母（請參閱上面的電子表格），但它不會影響算法的正確性。我們拒絕@deominators並循環到元素/ @ loop_end與步驟2以避免偶數。

將算法加速到320x的優化令人印象深刻。請參見下面的代碼下來：

class PrimeNumbers 

    def initialize(size) 
    raise ArgumentError if size < 2 
    prepare_vars(size) 
    end 

    def process 
    @array.each do |i| 
     next if @denominators.include?(i) 
     @prime.push(i) if test_of_prime(i) 
    end 
    @prime 
    end 

    private 

    def prepare_vars(size) 
    @prime = [2] 
    @array = 1.step(size,2).to_a 
    @array.shift 

    @loop_end  = (size**(1/3.0)).to_i 
    @loop_end  += 1 if (@loop_end % 2 == 0) 
    @denominators = [] 

    3.step(@loop_end-2,2).each do |i| 
     i.step(@loop_end-2,2).each do |k| 
     @denominators << i * k 
     end 
    end 
    end 

    def test_of_prime(e, is_prime = true) 
    3.step(e/@loop_end, 2) do |k| 
     if e % k == 0 
     is_prime = false 
     break 
     end 
    end 
    is_prime 
    end 

end 

單元測試是可用的樓下：

require 'minitest/autorun' 

class PrimeNumbersTest < Minitest::Unit::TestCase 

    def test_valid_1 
    assert_equal [2], PrimeNumbers.new(2).process 
    end 

    def test_valid_2 
    assert_equal [2, 3, 5, 7, 11], PrimeNumbers.new(11).process 
    end 

    def test_valid_3 
    assert_equal [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47], PrimeNumbers.new(50).process 
    end 

    def test_valid_4 
    assert_equal [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97], PrimeNumbers.new(100).process 
    end 

    def test_valid_5 
    assert_equal [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797], PrimeNumbers.new(800).process 
    end 

    def test_valid_6 
    assert_equal [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499], PrimeNumbers.new(1500).process 
    end 

    def test_valid_7 
    assert_equal [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993], PrimeNumbers.new(8000).process 
    end 

    def test_invalid_8 
    assert_raises(ArgumentError) { PrimeNumbers.new(1) } 
    end 

end 

UPDATE2

埃拉托色尼的篩算法是一種速度更快。