ブルーム整数

問題ステートメントは、ユーザー入力として入力される特定の数値が 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 を格納します。

• for ループで i=2 から i
• 4t 3 の形式で N の因数である素数が見つかった場合は、N をその素数で割った商を保存します。

• 商も素数で 4t 3 の形式の場合は true を返し、それ以外の場合は false を返します。

• 関数が true を返す場合、数値は blum 整数です。

＃＃＃例＃＃＃
• このメソッドの C コード -

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

時間計算量: O(N*log(log(N))
• 、これはエラトステネスのふるいの時間計算量であるためです。

空間計算量: O(N)

。素数を格納するためにサイズ N 1 の配列を使用するためです。

＃＃＃結論は＃＃＃

blum 整数の概念については、この記事で説明されています。この論文では、C のエラトステネスの篩の概念を使用して、数値が blum 整数であるかどうかをチェックする効率的な方法を提案します。

この記事を読んで、blum 整数の概念を明確に理解し、数値が blum 整数であるかどうかを確認する方法を理解できたことを願っています。

以上がブルーム整数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。