ブルーム整数-C++-php.cn

ブルーム整数

王林

リリース： 2023-08-29 18:41:06

転載

861 人が閲覧しました

ブルーム整数

問題ステートメントは、ユーザー入力として入力される特定の数値が Blum 数値であるかどうかを確認することで構成されています。

A Blum Integer は、個別の素因数 a および b が 4t 3 の形式である半素数です (t は正の整数)。半素数は、ちょうど 2 つの素数の積である数、またはちょうど 2 つの素因数を持つ自然数です。セミプライムの場合、係数は等しい場合があります。

数値 N が blum 整数の場合、1 と数値自体ではなく、N=a*b のように 2 つの因数だけを持たなければなりません。また、2 つの因数 a と b は異なる素数形式 4t 3 でなければなりません。 (任意の正の整数 t の場合)。

最初のいくつかの blum 整数は 21、33、57、69、77、93、129、133、141....

偶数の自然数はファジー整数にはなりません。2 つの非素因数の積 (4t 3 (つまり、奇数) の形式) は常に 20 より大きい奇数になるからです。

この問題では、数値 N が与えられ、その数値が blum 整数であるかどうかを確認する必要があります。

＃＃＃＃＃＃例＃＃＃＃＃＃リーリー

手順:

入力で指定された数値は 57 です。数字 57 は、19 と 3 の積 (つまり、19*3) として表すことができます。どちらの因数も 4t 3 の形式の異なる素数であるため。

19=4*4 3、この例の t の値は 4 です。 3=4*0 3、t の値は 0 です。

したがって、数値 57 は blum 整数です。

リーリー

手順:

与えられた数値は 49 で、7*7 で表すことができます。 7 は素数ですが、数値の場合は 2 つの異なる素数の積である必要があるためです。したがって、49 はファジー整数ではありません。

リーリー 説明:

数値 35 は、7 と 5 の積 (つまり、7*5) として表すことができます。両方の数値は異なる素数で、7 は 4t 3 の形式ですが、5 は t の整数値に対して 4t 3 として表すことができません。したがって、35 は曖昧な整数ではありません。

数値が blum 整数かどうかを確認するアルゴリズムを理解しましょう。＃＃＃アルゴリズム＃＃＃数値がブルーム整数であるかどうかを確認するには、その数値の前にある素数をすべて見つけて、4t 3 の形式の 2 つの異なる素数の積が指定された数値を形成できるかどうかを確認するだけです。

エラトステネスの篩

の概念を使用して、指定された数 N までのすべての素数を見つけます。エラトステネスの篩は、任意の数値 N に先行する素数の数を見つける最も効率的な方法です。

このメソッドでは、サイズ N 1 のブール配列を作成します。ここで、N は指定された数値です。数値が素数で、そのインデックス値がこの数値と等しい場合は true を格納し、それ以外の場合は配列に false を格納します。

非素数に対応するインデックス値 false を N まで更新するには、for ループで i=2 から i

i に対応する arr[i] の値が true の場合、ネストされたループで p=i*i から p

エラトステネスのふるいを使うと、1 から N までのすべての素数を得ることができます。ここで、配列の for ループを反復して、指定された数値 N の因数であり、形式 4t 3 の素数が存在するかどうかを確認します。また、素数を N で割った商も異なります。 4t 3 の形式の素数。上記の条件がすべて満たされている場合、指定された数値 N は blum 整数になります。そうでない場合は、整数ではありません。

問題を効率的に解決するために、このアルゴリズムをアプローチに使用します。

＃＃＃方法＃＃＃以下に、N が blum 整数かどうかを確認するアプローチでアルゴリズムを実装する手順を示します。 -

数値が blum 整数かどうかを確認する関数を作成します。

この関数では、エラトステネスのふるいの概念を使用して、対応するインデックスのサイズ N 1 から N までのブール配列内のすべての素数に対して true を格納します。