Pythonで約数の個数がK以下の要素をリストから抽出する方法

概要

Pythonを使って、リスト内の要素の中から「約数（因子）の個数がK以下」である要素だけを抽出する方法を紹介します。ここでは、2つの引数を受け取る関数を定義し、リスト内包表記で各要素を走査しながら、剰余演算子（%）を使って約数の個数を判定するアプローチを取ります。

サンプルコード

def factors(element, K):
    return len([index for index in range(1, element + 1) if element % index == 0]) <= K

my_list = [63, 112, 168, 26, 68]

print("The list is :")
print(my_list)

K = 5
print("The value for K is ")
print(K)

my_result = [element for element in my_list if factors(element, K)]

print("The result is :")
print(my_result)

出力結果

The list is :
[63, 112, 168, 26, 68]
The value for K is 
5
The result is :
[26]

コードの解説

• factors関数の定義： 要素elementと閾値Kを引数として受け取ります。1からelementまでの数値を順に確認し、「element % index == 0」（割り切れる）となる値、つまり約数だけをリスト内包表記で集めます。
• 約数の個数判定： 集めた約数リストの長さ（len）がK以下かどうかを比較し、その真偽値（True / False）を返します。
• リストの準備： サンプルとして [63, 112, 168, 26, 68] という整数のリストを定義し、コンソールに表示します。
• Kの設定： 閾値となる変数Kに5を代入します。
• リスト内包表記によるフィルタリング： 元のリストを走査し、各要素に対してfactors関数を呼び出します。戻り値がTrueになった要素だけが新しいリストに残ります。
• 結果の格納： フィルタリングされた結果は変数my_resultに代入されます。
• 出力： 最終的な結果がコンソールに表示されます。

各要素の約数の個数を検証

参考までに、サンプルリストの各要素の約数を実際に確認してみましょう。

• 63： 1, 3, 7, 9, 21, 63 → 6個（K=5より多いため除外）
• 112： 1, 2, 4, 7, 8, 14, 16, 28, 56, 112 → 10個（除外）
• 168： 1, 2, 3, 4, 6, 7, 8, 12, 14, 21, 24, 28, 42, 56, 84, 168 → 16個（除外）
• 26： 1, 2, 13, 26 → 4個（条件を満たすため採用）
• 68： 1, 2, 4, 17, 34, 68 → 6個（除外）

このように「約数の個数が5以下」という条件を満たすのは26だけであることが分かり、実行結果 [26] とも一致しています。

計算量を改善する高速化テクニック

上記の実装は非常にシンプルですが、各要素nに対して1からnまですべて確認するため、時間計算量はO(n)になります。大きな数を扱う場合は、「約数は平方根を境にペアで現れる」という性質を利用すると効率化できます。

import math

def factors_fast(element, K):
    count = 0
    for i in range(1, int(math.isqrt(element)) + 1):
        if element % i == 0:
            count += 2 if i != element // i else 1
            if count > K:
                return False
    return count <= K

iが約数であれば element // i も必ず約数になるため、約数をペアとして数えることで探索範囲を平方根までに抑えられます。また、途中で個数がKを超えた時点で即座にFalseを返すことで、無駄な計算も省けます。

まとめ

本記事では、関数とリスト内包表記を組み合わせて、約数の個数がK以下の要素をリストから抽出する方法を解説しました。まずはシンプルな実装でロジックを理解し、データサイズが大きくなったら平方根を活用した高速版へ切り替えるのがおすすめです。