为什么我的ruby编码找不到素数？
我想知道为什么我的代码不起作用。 我是代码世界的新手，所以如果有人能为我解决这个问题，那么最好如何解决它谢谢！
我正在尝试创建一个程序，它将指出我指定的数字列表中的素数。
请告诉我为什么这两个代码不起作用！ 我很困惑第二个代码试图做什么，因为我发现它是别人对我的问题的解决方案。 我是编码的新手，但我喜欢它，所以请耐心等待！
这是我的简单代码：
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美分我会很感激！ 哦，最后我如何正确地在问题板上发布代码？ 没有导师，我是如此新鲜，如此困惑！
你有一些问题。 之前确定了一个：声明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 % i != 0 ，该数字都是素数。 然而，那是不成熟的。 在确定所有小于num整数的num % i != 0之前，您无法得出该结论。
让我们看看如何解决这些问题。 我认为最简单的方法是编写一个单独的方法来确定单个数字是否为素数。 我把那个方法称为is_prime? is_each_prime?命名了主要方法is_each_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)).all? { |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
创建单独方法的一个优点是is_prime? 是你可以单独测试，以确保它正常工作。
素数不包括均数（当然除2），因此您可以在外部和内部循环中跳过它们。 一旦你发现数字是素数，就打破循环。 其中两种技术可以大大加快算法速度，我的实验是在10000arrays上从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
下一步是问这些问题：
- 哪里可以跳过偶数？
- 为什么甚至要遍历偶数？
- 为什么迭代超过某一点？
- 一旦传出一半arrays，有没有机会获得素数？
所以让我们看看算法快了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等。它有助于仅通过一小组数据忽略arrays的其余部分。 请参阅下图中的更多详细信息：
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数组大于实际分母（参见上面的电子表格），但它不会影响算法的正确性。 我们拒绝@denominators并使用步骤2循环到element / @ loop_end以避免偶数。
对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
unit testing可在下面找到：
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
筛选Eratosthenes算法的速度更快。
你在循环之外初始化了i ，所以随后的数字开始于i已经设置为某个高值的测试。