iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 28
0
自我挑戰組

Codewar 進進出出 JS/Ruby系列 第 28

下一個質數

題目:
(6 級) Steps in Primes
質數和質數之間沒有固定的間隔,例如從 2 到 3 的間隔是 1;從 3 到 5 的間隔是 2;從 7 到 11 的間隔是 4。在 2 到 50 之間,間隔為 2 的質數有以下這些:
[3, 5] - [5, 7] - [11, 13] - [17, 19] - [29, 31] - [41, 43]

我們要寫一個可以判斷質數間隔的 function:
g (大於等於 2 的整數) 表示要判定的間隔
m (大於等於 2 的整數) 表示起始數字 (包含 m)
n (大於等於 m 的整數) 表示結束數字 (包含 n)

在上面的範例中 (2, 2, 50) 會回傳 [3, 5] 作為第一對符合規則的質數。
因此,如果有找到符合的質數,就回傳第一對找到的質數,若沒有則回傳 nilnull

範例:

step(2, 5, 7) --> [5, 7] or (5, 7) or {5, 7} or "5 7"

step(2, 5, 5) --> nil or ... or [] in Ocaml or {0, 0} in C++

step(4, 130, 200) --> [163, 167] or (163, 167) or {163, 167}

Ruby 解法:

require "prime"

def step(g, m, n)
  primes = []
  steps = []
  
  (m..n).each do |n|
    primes << n if Prime.prime?(n)
  end
  
  primes.each do |prime_a|
    break if steps.size > 0
    
    primes.each do |prime_b|
      if prime_b - prime_a == g
        steps += [prime_a, prime_b]
      break
      end
    end
  end
  
  steps.size > 0 ? steps : nil
end

心得:
一開始用上面的寫法但是最後一個 test 會出現 code timeout 問題,看了解答之後發現有個很好用的 find 方法

於是就把寫法改成:

require "prime"

def step(g, m, n)
  # 準備放結果用的陣列
  steps = []
  
  (m..n).find do |i|
    # 如果 i 和 i + g 的數字皆為質數
    # 就把這兩個質數放進 steps
    steps += [i, i + g] if i.prime? and (i + g).prime?
  end
  
  # 回傳 steps,但如果為空陣列則回傳 nil
  steps.size > 0 ? steps : nil
end

JavaScript 解法:

function step(g, m, n) {
  // 先寫一個判斷質數的方法
  const isPrime = num => {
    for(let i = 2; i < num; i++)
      if(num % i === 0) return false;
    return num > 1;
  }
  
  // 準備放結果用的陣列
  let steps = []
  for (let i = m; i < n; i++) {
    // 如果 i 和 i + g 的數字皆為質數
    if (isPrime(i) && isPrime(i + g)) {
      // 就把這兩個質數放進 steps
      steps.push(i)
      steps.push(i + g)
      // 並且中斷迴圈
      break;
    }
  }
  
  // 回傳 steps,但如果為空陣列則回傳 null
  return steps.length > 0 ? steps : null
}

上一篇
我是新來的
下一篇
你今天重複了嗎?
系列文
Codewar 進進出出 JS/Ruby30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言