n 未満の 3 次自由数

三次因数のない数値は、因数として三次数値を持たない数値を指します。

三次数因数は、三次数である整数であり、剰余なしで数値を割ることができます。

たとえば、8 は 3 乗因数 2 (2*2*2 = 8) であり、8 を 16 で割った余りは 0 であるため、8 は 3乗因数 16 です。

したがって、8 も 16 も立方体のない数ではありません。

指定された数値 n より小さいすべての立方体のない数値を検索します。

Example

Example

説明

説明

1、8、16 はリストにないことに注意してください。 1 と 8 はそれ自体が 3 次の数であり、16 は 8 の倍数であるためです。

この問題を解決するには 2 つの方法があります。

方法 1: 暴力による方法

総当たりクラッキングの方法は次のとおりです:

すべての数値を n までたどります。
各数値について、そのすべての約数を繰り返します。
数値のいずれかの因数が立方体である場合、その数値は立方体なしではありません。
それ以外の場合、これらの数の約数がいずれも 3 次でない場合、その数は 3 乗のない数になります。
数字を出力します。
Example

Example

このアプローチのプログラムは次のとおりです。 -

次は、指定された数値 n より小さいすべての立方体のない数値を出力する C プログラムです。

方法 2: エラトステネスのふるいテクニック

この問題を解決する非常に効率的な方法は、エラトステネスの篩の概念です。

指定された制限より小さい素数を見つけるために使用されます。ここでは、3次数ではない数値をフィルタリングして、解を取得します。

方法は次のとおりです-

サイズ n のブール値リストを作成します。

• すべての数値を true としてマークします。これは、現在すべての数値をキューブレスとしてラベル付けしていることを意味します。

• n 未満の可能なすべてのキューブを走査します。

• n 未満の 3 次数の倍数をすべてスキャンします。

• リスト内のこれらの倍数をすべて false としてマークします。これらの数値はキューブフリーではありません。

• リストを調べます。リスト内のまだ真である数値を出力します。

• 出力には、n 未満のすべての立方体なし数値が含まれます。

• Example

  の翻訳は次のとおりです。
Example

このアプローチのプログラムは次のとおりです。 -

次の C プログラムは、エラトステネスのふるいを使用して、指定された数値 n 未満のすべての立方体のない数値を出力します。

この記事では、n より小さい立方体のない数を見つける問題を解決します。強引な方法とエラトステネスの篩を使った効率的な方法の 2 つの方法を見ました。

C プログラムは、これら 2 つのメソッドの実装を提供します。

以上がn 未満の 3 次自由数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。