为什么我的红宝石编码找不到素数？
Nor*_*ang 3 ruby algorithm primes
我想知道为什么我的代码不起作用.我是代码世界的新手,所以如果有人能为我解决这个问题,那么最好如何解决它,谢谢!
我正在尝试创建一个程序,它将从我指定的数字列表中指示素数.
请告诉我为什么这两个代码不起作用!我很困惑第二个代码试图做什么,因为我发现它是别人对我的问题的解决方案.我是编码的新手,但我喜欢它,所以请耐心等待!
这是我的简单代码:
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美分我会很感激!哦,最后我如何正确地在问题板上发布代码？没有导师,我是如此新鲜,如此困惑!
Ana*_*oly 10
素数不包括均数(当然除了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
下一步是问这些问题:
- 哪里可以跳过偶数？
- 为什么要甚至遍历偶数？
- 为什么迭代超过某一点？
- 一旦传出一半阵列,有没有机会获得素数？
所以让我们看看算法快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)
选择性阻止是什么？让我们选择数组大小,例如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个元素以选择素数就足够了.如果输入更大,@ toop_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
单元测试如下:
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算法的速度更快.