ruby - 为什么我用于查找素数的 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

素数不包括偶数(当然 2 除外)，因此您可以在外循环和内循环中跳过它们。一旦你发现数字是素数，就打破循环。这两项技术可显着加快算法速度，我在 10000 个阵列上进行的实验从 3.9 秒降至 0.2 秒。

标准低效算法优先:

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. 数组过半后有机会得到素数吗？

让我们看看速度提高了 30 倍的算法(输入 50000 大小，与第一个算法版本相比用了 3 秒而不是 98 秒):

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 不可能是 Integer。为什么要砍第三？有很强的依赖性。查看奇数的分隔符:

更新:

深入研究算法后，我发现无需遍历初始数组的一半甚至三分之一大小。最后，您可以迭代少于 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)

什么是选择性 block ？让我们选择数组大小，例如 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]

Maximum number of values you need to loop through is 5% (19/20)! So to compare a given value no need to loop more than first 5-10% of values.

对于该算法来说，循环遍历 421 个元素以选择素数就足够了。如果输入更大，@loop_end 将适应。在较小的数据集(1000 个值)上，变量是:

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

遍历 111 个元素有助于从 1000 个元素的数组中找出素数。虽然 @denominators 数组比实际的分母大(见上面的电子表格)，但它不影响算法的正确性。我们拒绝 @denominators 并使用第 2 步循环到 element/@loop_end 以避免偶数。

将算法速度提高 320 倍的优化确实令人印象深刻。请参阅下面的代码:

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

更新 2

埃拉托色尼筛法算法速度更快。