2026-11-11
Coprime.hs
pairwiseCoprime :: [Int] -> Bool
整数のリスト xs から異なる位置の2つの要素をどう選んでも、その最大公約数が1なら True、そうでなければ False を返す pairwiseCoprime を書いてください。要素はすべて1以上です。要素が1つ以下のときは、選べる組が無いので True です。
入力例 1
pairwiseCoprime [3, 5, 7]
出力例 1
True
入力例 2
pairwiseCoprime [4, 9, 10]
出力例 2
False
入力例 3
pairwiseCoprime []
出力例 3
True
Reference
Reference
import Data.List (tails)
pairwiseCoprime :: [Int] -> Bool
pairwiseCoprime xs = and [gcd a b == 1 | (a : bs) <- tails xs, b <- bs]
tails xs は xs の後ろの部分を長い順に並べたリストで、[4, 9, 10] なら [[4, 9, 10], [9, 10], [10], []] です。内包表記で各要素を (a : bs) と受けると、a とそれより後ろの要素 b の組がちょうど1回ずつ作られます。すべての組で gcd a b == 1 なら and が True を返します。これは参考実装で、唯一の正解ではありません。
入力例2で、隣り合う 4 と 9、9 と 10 の最大公約数はどちらも1ですが、離れた 4 と 10 は2を共有しています。隣どうしだけを調べると、この組を見落として True を返してしまいます。空リストと1要素のリストでは組が1つも作られず、and [] は True なので、境界の場合を別に書く必要はありません。最後の [] はパターン (a : bs) に一致せず、内包表記の中では一致しない要素が読み飛ばされます。