Pythonの完全数プログラム：数が完全かどうかを確認する方法は？

公開: 2021-01-29

序章

適切な除数の合計（数自体を含まない）が数と等しい場合、その数は完全数であると言われます。

より良いアイデアを得るために、例を考えてみましょう。6の適切な約数は1、2、3です。これらの約数の合計は6（1 + 2 + 3 = 6）に等しいので、6は完全数であると言われます。 。 一方、12のような別の数を考えると、12の適切な除数は1、2、3、4、6です。これらの約数の合計は12に等しくないため、12は完全数ではありません。

Pythonでのプログラミングは、構文が単純で読みやすいため、他の言語と比較すると比較的単純で楽しいものです。 完全数の概念が明確になったので、Pythonプログラムを作成して、数が完全数であるかどうかを確認しましょう。 指定されたユーザー入力が完全数であるかどうかを確認するためのPythonコードを作成し、Pythonを使用したコーディングの楽しさを探りましょう。 専門知識を習得したい場合は、データサイエンスプログラムをご覧ください。

読む： Pythonパターンプログラム

目次

Pythonプログラム

完全数を見つけるための基本的な解決策は、2をnumber-1にループし、適切な除数の合計を維持し、合計が数と等しいかどうかを確認することです。

n = int（input（ "数値を入力"））
合計=1
範囲（2、n）のiの場合：
if（n％i == 0）：
sum = sum + i
if（sum == n）：
print（n、”は完全数です”）
そうしないと：
print（n、”完全数ではありません”）

コードを見ていきましょう。

デフォルトではユーザー入力はPythonで文字列として読み取られるため、最初にユーザー入力でnを初期化し、整数に型キャストします。 nが完全数であるかどうかを確認する必要があります。 1はすべての整数（ゼロを除く）の適切な除数であるため、合計を1で初期化していることに注意してください。これにより、ループ内の反復を除外して、2から直接開始できます。

2を数値1にループし、整数を加算して、それが適切な除数である場合は合計します。 そして最後に、ループから抜け出すときに、得られた合計が数値と等しいかどうかをチェックしています。 ケーキでしょ？

少し最適化されたバージョン

上記のプログラムをドライランした後、それを最適化できるかどうか疑問があるかもしれません。 ただし、アルゴリズムを変更せずに、反復回数を2回に減らすことができます。 なぜなら、数は数/2より大きい適切な除数を持つことができないという考えを得たからです。

n = int（input（ "数値を入力"））
合計=1
範囲内のiの場合（2、n // 2 + 1）：
if（n％i == 0）：
sum = sum + i
if（sum == n）：
print（n、”は完全数です”）
そうしないと：
print（n、「完全数ではありません」）

上記のスニペットは前のスニペットとほぼ同じですが、number/2までルー​​プする点が異なります。 整数除算を実行してfloat型に変換されないようにしていることに注意してください。また、範囲内の最後の整数はPythonループで考慮されないため、n // 2+1までループしています。

制限事項

与えられた範囲で完全数を見つけるように求められた場合、私たちのソリューションは、number ^ 2に比例する時間を消費します。つまり、O（n²）の時間計算量です。 指定された範囲内の各数値をループしてから、各数値の適切な除数を確認する必要があるためです。 そして、完全数条件を満たす数はほとんどありません。 たとえば、0から1000の範囲の完全数の数はわずか3（6、28、496）です。

適切な除数を見つけるためにすべての要素をループする必要がない、これに対する最適化されたソリューションがあります。Euclidの式は、2 n −1（2 n − 1）は、n、（2 n − 1）の両方が素数。 たとえば、6はnを2として上記の方程式を満たし、2、2 2 − 1（2 2 − 1 = 3）は両方とも素数です。 しかし、奇数の完全数があるかどうかを調べるように求められた場合、答えることはできません。

また、すべての言語には、格納できる整数の範囲に制限があることもわかっています。 この制限により、最大の完全数を見つける方法がない場合があります。

入力数が大きい場合、これらすべての制限に直面しますが、入力数が小さい場合、最初のソリューションはより短い時間で機能します。

また読む： Web開発のためのPythonフレームワーク

結論

私たちはその定義を知っており、完全数の背後にある概念を理解しています。 数を見つけるための基本的な解決策をウォークスルーしたのは、完全数であるかどうかです。 そして、最初のソリューションを見た後、反復回数を減らすことで少し最適化しました。 アルゴリズムの限界を乗り越え、完全数を見つけるためのEuclidの公式について説明しました。

これで、Pythonプログラムを認識して、数値が完全数であるかどうかを確認できます。 自分でコードを書いてみて、重複する反復が見つかった場合は最適化してみてください。 また、与えられた数の範囲で完全数を見つけるためのコードを作成してみてください。

python、データサイエンスについて知りたい場合は、IIIT-BとupGradのデータサイエンスのエグゼクティブPGプログラムをご覧ください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップ、業界の専門家とのメンターシップを提供します。 、業界のメンターと1対1で、400時間以上の学習とトップ企業との仕事の支援。

Pythonの完全数プログラムの複雑さを説明します。

除数の合計に等しい数は、完全数であると言われます。 数値が完全かどうかを確認するには、2つの方法があります。 最初のアプローチは、各「i」に対して「j」回反復し、その除数をチェックするため、時間計算量がO（n2）である単純なアプローチです。
2番目のアプローチは、時間計算量がO（√n）である最適化されたソリューションです。 ここでは、すべての数値を繰り返す必要はありません。 Euclidの式を使用して、次のように直接結論付けることができます。
2n−1（2n − 1）、ここでnと2nは素数です。
ただし、この式は奇数の完全数では機能しないため、別のアプローチを見つける必要があります。

完全数プログラムのアプローチの制限は何ですか？

これらのアプローチはどちらも優れていますが、ある程度しかありません。 いくつかの技術的な理由から、どちらも完璧なアプローチとは見なされません。 これらのアプローチの制限は次のとおりです。

1.最初の単純なアプローチは、多くの時間とメモリを消費し、時間計算量がO（n2）であるため、より悪くなります。 これは、ネストされたループを使用しており、外側のループのすべての要素に対して内側のループをn回反復しているためです。 このアプローチは単純であり、nの値が大きい場合はTLEが得られるため、お勧めしません。
2.次に、O（√n）の問題を解決する最適化されたアプローチがあります。 奇数の完全数が関係しない限り、これは良いアプローチです。 このアプローチは、偶数の完全数に対してのみ機能する「偶数の完全数に対するEuclidの公式」に基づいているため、奇数の完全数をチェックすることはできません。

Pythonは競技プログラミングに適していますか？

PythonはC/C ++、さらにはJavaから進化し、研究開発の目的に最も適した言語であると考えられています。 しかし、競技プログラミングに関しては、プログラミングコミュニティの大多数はPythonを避けています。 Pythonである理由は、これら3つの言語の中で最も遅いです。