o1-mini-2024-09-12· OpenAI
WildChat-4.8M (AI2)
指定された範囲の素数を高速で探すコードを書いてください
- User
指定された範囲の素数を高速で探すコードを書いてください
- Assistant
指定された範囲内の素数を高速に見つけるためには、「エラトステネスの篩(ふるい)」を利用した「セグメント篩(せぐめんとふるい)」という手法が有効です。以下に、Pythonで実装したセグメント篩のコードを提供します。このコードは、大きな範囲でも効率的に素数を見つけることができます。
import math import sys def sieve(limit): """エラトステネスの篩を用いてlimit以下の素数を全て求める関数""" is_prime = [True] * (limit + 1) is_prime[0:2] = [False, False] for num in range(2, int(math.isqrt(limit)) + 1): if is_prime[num]: is_prime[num*num : limit+1 : num] = [False] * len(range(num*num, limit+1, num)) primes = [num for num, prime in enumerate(is_prime) if prime] return primes def segmented_sieve(a, b): """セグメント篩を用いて範囲[a, b]の素数を全て求める関数""" if a > b: return [] a = max(a, 2) limit = int(math.isqrt(b)) + 1 primes = sieve(limit) segment_size = b - a + 1 is_prime = [True] * segment_size for prime in primes: start = max(prime * prime, ((a + prime - 1) // prime) * prime) for multiple in range(start, b + 1, prime): is_prime[multiple - a] = False primes_in_range = [num for idx, num in enumerate(range(a, b + 1)) if is_prime[idx]] return primes_in_range def main(): if len(sys.argv) != 3: print("使用方法: python primes.py 開始値 終了値") sys.exit(1) a = int(sys.argv[1]) b = int(sys.argv[2]) primes = segmented_sieve(a, b) print(f"{a} から {b} までの素数:") print(primes) if __name__ == "__main__": main()使用方法
-
コードの保存: 上記のコードを
primes.pyという名前で保存します。 -
実行: コマンドラインから以下のように実行します。
python primes.py 開始値 終了値例えば、10から50までの素数を探したい場合は、
python primes.py 10 50と入力します。
コードの説明
-
エラトステネスの篩 (
sieve関数):- 指定された
limit以下の素数を全て求めます。 is_primeリストを用いて各数が素数かどうかを管理します。
- 指定された
-
セグメント篩 (
segmented_sieve関数):- 範囲
[a, b]内の素数を見つけるために、まずsqrt(b)までの素数をエラトステネスの篩で求めます。 - その素数を用いて、範囲
[a, b]内の数をふるい落とし、素数のみを残します。
- 範囲
-
メイン処理 (
main関数):- コマンドライン引数として開始値と終了値を受け取り、
segmented_sieve関数を呼び出して素数を取得します。 - 結果を表示します。
- コマンドライン引数として開始値と終了値を受け取り、
パフォーマンスの最適化ポイント
- メモリ効率: セグメント篩を使用することで、大きな範囲でもメモリ使用量を抑えつつ素数を見つけられます。
- 計算の削減: 既知の小さい素数のみを使用して範囲内の合成数を効率的に排除します。
補足
- 非常に大きな範囲(例えば 以上)での素数探索には、さらなる最適化や高度なアルゴリズム(例:並列処理やビット操作)を検討する必要があります。
- Pythonは高級言語であり、他の言語(例えばC++)に比べて一般的に実行速度は遅いですが、普通の範囲では十分な速度が得られます。速度が重要な場合は、C++への実装を検討してください。
参考リンク
-