C++ で、次を中国語に翻訳します。 L と R の間で、P と互いに素な数値の数を数えます。

コンピューター プログラミングの世界では、指定された範囲内で特定の数値と互いに素な数値の数を見つけることは一般的なタスクとなることがあります。相対素数とも呼ばれる相対素数は、1 以外に共通約数を持たない数です。この記事では、C 言語を使用して、与えられた整数 L と R の間で特定の数 P と互いに素な数の数を求める方法を検討します。

＃＃＃文法＃＃＃

最初に、次のコード例で使用するメソッドの構文の概要を説明します -

リーリー ＃＃＃アルゴリズム＃＃＃

互いに素な数の数を計算するために使用するアルゴリズムは次のとおりです -

変数 count を 0 に初期化します。これは、素数の数を格納するために使用されます。

• L から R まで各数値 num を繰り返します。

• 各数値について、P と互いに素であるかどうかを確認します。

• num と P が互いに素な場合、カウントを 1 増やします。

• count の最終値を返します。

• 方法 1: 素朴な方法

最初に説明する方法は単純な方法です。ユークリッドのアルゴリズムを使用して P との互いに素性を検証するには、この方法では指定された範囲内の各数値を繰り返しチェックする必要があります。

Example

の中国語訳は次のとおりです:

Example

リーリー ＃＃＃出力＃＃＃ リーリー

説明

の中国語訳は次のとおりです:

説明

countCoprimes 関数は、L (範囲の開始値)、R (範囲の終了値)、および P (P の値) の 3 つのパラメーターを受け入れます。

countCoprimes 関数内で、変数 count を 0 に初期化し、互いに素数の数を保存します。

for ループは、L から R まで各数値 num を繰り返します。

ループ内で、変数 a と b をそれぞれ num と P に初期化します。

while ループでユークリッド アルゴリズムを使用し、モジュラー演算を繰り返し交換して実行することで、a と b の最大公約数 (GCD) を見つけます。

GCD (a に格納) が 1 に等しい場合、これは num と P が互いに素であることを意味します。この場合、count 変数をインクリメントします。

すべての数値を慎重に繰り返し、完了したらカウント値を返すことでカウント値を最終的に決定します。

メイン関数は、L、R、P 変数に適切な値を慎重に割り当てます。

次に、指定された値を使用して countCoprimes 関数を呼び出し、結果を result 変数に保存します。

最後に、L と R の間で P と相対的に素な数値の数を表示します。

方法 2: 素因数分解

この戦略には、P の素因数分解を利用して、L と R の間にある互いに素な整数の数を正確に計算することが含まれます。

Example

の中国語訳は次のとおりです:

Example

リーリー ＃＃＃出力＃＃＃ リーリー

説明

の中国語訳は次のとおりです:

説明

countCoprimes 関数は、L (範囲の開始値)、R (範囲の終了値)、および P (P の値) の 3 つのパラメーターを受け入れます。

P の素因数を格納するための順序なし因数セットを作成します。一時変数 tempP を P に初期化します。

2 から tempP の平方根まで繰り返します。 tempP が i で割り切れる場合、因数のセットに i を追加し、tempP が i で割り切れなくなるまで tempP を i で割ります。

上記のループの後、tempP が 1 より大きい場合、それは素数であり、因数に追加する必要があることを意味します。

変数 count を 0 に初期化し、互いに素な数の数を保存します。

L から R まで各数値 num を反復処理し、設定された因数のいずれかの因数で割り切れるかどうかを確認します。可能であれば、非共素というラベルを付けます。

すべての数値の反復が完了すると、結果のカウントが最終値として返されます。 main関数としては、L、R、Pを指定された値で初期化します。

次に、指定された値を使用して countCoprimes 関数を呼び出し、結果を result 変数に保存します。

最後に、L と R の間で P と相対的に素な数値の数を表示します。

＃＃＃結論は＃＃＃

指定された範囲 L-R 内の共素数を計算し、特定の値 P を満たすことは、プログラマーにとって良い課題です。しかし、コード レベルでは、最善のアプローチは何でしょうか?この記事の一部として、このような問題を解決する際に実際の効率を提供する 2 つの C の使用例を詳しく説明します。まず、ターゲット区間内のすべての値を反復処理し、ユークリッド アルゴリズムを使用して数値が互いに素数として一致するかどうかを確認し、さらに最適化戦略を使用するオイラー関数法を使用します。どの方法を使用するかに関係なく、それを最大限に活用できるかどうかは、選択する数値や指定する間隔などの状況要因に大きく依存しますが、可能な 2 つの方法の間で賢明に選択することで、全体的な速度が大幅に向上します。プログラムの速度。技術的なスキルと創造的な問題解決能力に技術的な知識を加えたいと考えているプログラマーにとって、これらの方法で C を使用した素数の数え方をマスターすることは、まさに必要なことかもしれません。

以上がC++ で、次を中国語に翻訳します。 L と R の間で、P と互いに素な数値の数を数えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。