題目:
(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]
作為第一對符合規則的質數。
因此,如果有找到符合的質數,就回傳第一對找到的質數,若沒有則回傳 nil
或 null
。
範例:
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
}