为什么我的红宝石编码找素数不起作用？
为什么我的红宝石编码找素数不起作用？
提问于 2014-11-07 02:17:01
我想知道为什么我的代码不起作用。我是新的代码世界，所以如果有人可以为我打破这个问题，如何最好地解决它，谢谢！
我正在尝试创建一个程序，它将从我指定的数字列表中指示素数。
请告诉我为什么这两个代码不工作！我对第二段代码试图做什么感到困惑，因为我发现它是别人解决我的问题的方法。我对编码很陌生，但我喜欢它，所以要忍受我自己！
以下是我的简单代码：
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....Why，这不起作用吗？我怎么才能让它起作用？它一直给我一个奇怪的答案，因为它粘在我的第一个数字上，而且似乎没有处理我插入的下一个数字：
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美分，我会很感激的！最后，我该如何正确地将代码贴在问题板上呢？没有良师益友，我是如此的新，如此的困惑！
回答 3
Stack Overflow用户
回答已采纳
发布于 2014-11-07 03:04:31
你有一些问题。其中一个是在前面确定的:语句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 % i != 0小于num，否则不能得出这个结论。
让我们看看如何解决这些问题。我认为最简单的方法是编写一个单独的方法来确定单个数字是否为素数。我已经将该方法称为is_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?的一个优点是可以单独测试它，以确保它正常工作。
Stack Overflow用户
发布于 2015-09-27 10:01:38
素数排除了偶数(当然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下一步是提出以下问题：
- 哪里可以跳过偶数？
- 为什么还要迭代偶数？
- 为什么要迭代超过某个点？
- 当你传递数组的一半时，有没有机会拥有素数？
因此，让我们看看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不可能是整数。为什么要切第三？有很强的依赖性。查看分隔符以获得奇数：
更新
深入研究算法，我发现不需要遍历初始数组的一半甚至三分之一大小。最后，您可以遍历不到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个元素数组中找出素数。尽管@分母数组比实际分母大(见上面的电子表格)，但它并不影响算法的正确性。我们拒绝@分母，并用步骤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
endUPDATE2
筛分的Eratosthenes算法是一种更快的方法。
Stack Overflow用户
发布于 2014-11-07 02:21:34
您在循环之外初始化了i，因此后续的数字首先使用已经设置为高值的i进行测试。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26792960
复制相关文章
相似问题
腾讯云开发者
