ホームページ バックエンド開発 Python チュートリアル Python で効率的に素数を生成するためにエラトステネスのふるいを最適化するにはどうすればよいでしょうか?

Python で効率的に素数を生成するためにエラトステネスのふるいを最適化するにはどうすればよいでしょうか?

Nov 28, 2024 pm 12:00 PM

How Can We Optimize the Sieve of Eratosthenes for Efficient Prime Number Generation in Python?

エラトステネスのふるい: Python での素数生成の最適化

エラトステネスのふるいは、素数を見つけるための古典的なアルゴリズムです。ただし、パフォーマンスのボトルネックを回避するには、正しく実装することが重要です。

元の実装

提供された primes_sieve 関数は、候補素数のリストを維持し、非素数を繰り返し削除します。リストを調べて因数を削除することで素数を決定します。このアプローチは、リスト操作のコストが高いため、本質的に非効率です。

辞書ベースの最適化

改良された primes_sieve1 関数は、辞書を使用して素数フラグを格納します。リストベースのアプローチよりも高速ではありますが、依然として課題に直面しています。未定義の順序で辞書を反復処理するため、非素因数の冗長なマーク付けが発生します。さらに、最終的な辞書をリストに変換するため、不要なオーバーヘッドが発生します。

正しく効率的な実装

正しいエラトステネスのふるいアルゴリズムは、ブール フラグのリストを利用して、素数性を示します。 primes_sieve2 関数は、すべての数値のフラグを True に初期化し、0 と 1 のフラグを False に設定します。リストを反復処理し、フラグを False に設定して素数以外をマークします。

このアプローチは次の理由から効率的です。

  • 辞書の代わりにリストを使用し、オーバーヘッドを回避します。
  • 素因数のみを非素数としてマークし、冗長性を削減します。
  • 各素数の 2 倍ではなく 2 乗から開始することで、マーキング プロセスを最適化します。

エラトステネスのふるいを正しく実装することで、パフォーマンスを大幅に向上させることができます。素数の生成により、200 万未満の素数を見つけるなどの大きな入力制限にも適しています。

以上がPython で効率的に素数を生成するためにエラトステネスのふるいを最適化するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Python vs. C:比較されたアプリケーションとユースケース Python vs. C:比較されたアプリケーションとユースケース Apr 12, 2025 am 12:01 AM

Pythonは、データサイエンス、Web開発、自動化タスクに適していますが、Cはシステムプログラミング、ゲーム開発、組み込みシステムに適しています。 Pythonは、そのシンプルさと強力なエコシステムで知られていますが、Cは高性能および基礎となる制御機能で知られています。

2時間でどのくらいのPythonを学ぶことができますか? 2時間でどのくらいのPythonを学ぶことができますか? Apr 09, 2025 pm 04:33 PM

2時間以内にPythonの基本を学ぶことができます。 1。変数とデータ型を学習します。2。ステートメントやループの場合などのマスター制御構造、3。関数の定義と使用を理解します。これらは、簡単なPythonプログラムの作成を開始するのに役立ちます。

Python:ゲーム、GUIなど Python:ゲーム、GUIなど Apr 13, 2025 am 12:14 AM

PythonはゲームとGUI開発に優れています。 1)ゲーム開発は、2Dゲームの作成に適した図面、オーディオ、その他の機能を提供し、Pygameを使用します。 2)GUI開発は、TKINTERまたはPYQTを選択できます。 TKINTERはシンプルで使いやすく、PYQTは豊富な機能を備えており、専門能力開発に適しています。

2時間のPython計画:現実的なアプローチ 2時間のPython計画:現実的なアプローチ Apr 11, 2025 am 12:04 AM

2時間以内にPythonの基本的なプログラミングの概念とスキルを学ぶことができます。 1.変数とデータ型、2。マスターコントロールフロー(条件付きステートメントとループ)、3。機能の定義と使用を理解する4。

Python vs. C:曲線と使いやすさの学習 Python vs. C:曲線と使いやすさの学習 Apr 19, 2025 am 12:20 AM

Pythonは学習と使用が簡単ですが、Cはより強力ですが複雑です。 1。Python構文は簡潔で初心者に適しています。動的なタイピングと自動メモリ管理により、使いやすくなりますが、ランタイムエラーを引き起こす可能性があります。 2.Cは、高性能アプリケーションに適した低レベルの制御と高度な機能を提供しますが、学習しきい値が高く、手動メモリとタイプの安全管理が必要です。

Pythonと時間:勉強時間を最大限に活用する Pythonと時間:勉強時間を最大限に活用する Apr 14, 2025 am 12:02 AM

限られた時間でPythonの学習効率を最大化するには、PythonのDateTime、時間、およびスケジュールモジュールを使用できます。 1. DateTimeモジュールは、学習時間を記録および計画するために使用されます。 2。時間モジュールは、勉強と休息の時間を設定するのに役立ちます。 3.スケジュールモジュールは、毎週の学習タスクを自動的に配置します。

Python:主要なアプリケーションの調査 Python:主要なアプリケーションの調査 Apr 10, 2025 am 09:41 AM

Pythonは、Web開発、データサイエンス、機械学習、自動化、スクリプトの分野で広く使用されています。 1)Web開発では、DjangoおよびFlask Frameworksが開発プロセスを簡素化します。 2)データサイエンスと機械学習の分野では、Numpy、Pandas、Scikit-Learn、Tensorflowライブラリが強力なサポートを提供します。 3)自動化とスクリプトの観点から、Pythonは自動テストやシステム管理などのタスクに適しています。

Python:自動化、スクリプト、およびタスク管理 Python:自動化、スクリプト、およびタスク管理 Apr 16, 2025 am 12:14 AM

Pythonは、自動化、スクリプト、およびタスク管理に優れています。 1)自動化:OSやShutilなどの標準ライブラリを介してファイルバックアップが実現されます。 2)スクリプトの書き込み:Psutilライブラリを使用してシステムリソースを監視します。 3)タスク管理:スケジュールライブラリを使用してタスクをスケジュールします。 Pythonの使いやすさと豊富なライブラリサポートにより、これらの分野で優先ツールになります。

See all articles