왜 루비는 소수를 찾기 위해 코딩하지 않습니까?

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. 이 코드가 고정되어 있습니다. 당신이 수를 결정했습니다 num % i == 0

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에 비해 모두 큰 숫자 덜 나눌 수 있는지 확인하기 위해 검사를 계속합니다. num % i == 0 때마다 그것이 소수가 아니라는 것을 인쇄합니다. 요점은 소수가 소수가 아니라고 판단한 후에도 계속 점검 할 필요가 없다는 것입니다.

또 다른 문제는 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을 초기화 했으므로이 이미 높은 값으로 설정되어 테스트를 시작합니다.

Answer 3

프라임 숫자는 evens (물론 2 제외)를 제외하므로 외부 및 내부 루프에서 프라임 숫자를 건너 뛸 수 있습니다. 번호가 소수라는 것을 알게되면 루프를 깰 수 있습니다. 이 두 기술은 알고리즘을 극적으로 가속화합니다. 실험은 3.00 초에서 10000 배열에서 0.2 초입니다.첫째

표준 inneficient 알고리즘 :

1. 도 숫자를 건너 뛸 :

   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 
   

   다음 단계는 이러한 질문을하는 것입니다?

2. 심지어 짝수를 반복하는 이유는 무엇입니까?
3. 특정 시점을 넘어서 반복하는 이유는 무엇입니까?
4. 배열의 절반을 전달하면 소수를 가질 수 있습니까? 그래서

의가 30 배 빠른 알고리즘을 보자는 (입력 50000 크기는 대신 98sec의 3 초 첫 번째 알고리즘 버전으로 비교했다) : 알고리즘의 효율성 시간의 결과에 따라 다름

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를 들어, 배열의 크기를 선택하자 변수를 통해 참조 : 5 % (19/20)입니다 통해

이

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 ~ 10 % 값 이상을 반복 할 필요가 없습니다.

알고리즘의 경우 421 개의 요소를 반복하여 소수를 선택하면 충분합니다. 더 큰 입력의 경우 @loop_end가 적용됩니다. 작은 데이터 세트 (1000 개 값)에서 변수는 다음과 같습니다.

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

루프 요소 111 개는 1000 개 요소 배열에서 소수를 찾습니다. @denominators 배열은 실제 분모보다 크지 만 (위의 스프레드 시트 참조) 알고리즘의 정확성에는 영향을 미치지 않습니다. 우리는 @denominators를 거부하고 짝수를 피하기 위해 2 단계에서 요소/@ 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 알고리즘은 빠른 방법이다 체 에라 토 스테 네스의

합니다.