4

それを取得する 1 つの方法は、自然数 (1,.., n ) をそれぞれ因数分解し、素因数が繰り返されているかどうかを確認することですが、n が大きい場合は時間がかかります。1,.., nから二乗のない数値を取得するより良い方法はありますか?

4

9 に答える 9

12

EratosthenesSieveの修正バージョンを使用できます。

ブール配列1を取ります。.n ;

n未満のすべての正方形を事前計算します。それはO（sqrt（N））;です。

各正方形とその倍数について、bool配列エントリをfalseにします...

于 2011-03-15T14:37:03.783 に答える
7

頭に浮かぶ最も直接的なことは、nまでの素数をリストし、それぞれの素数を最大で1つ選択することです。これは大きなnの場合は簡単ではありませんが（たとえば、ここに1つのアルゴリズムがあります）、この問題がどちらかであるかどうかはわかりません。

于 2011-03-15T14:34:23.680 に答える
7

http://mathworld.wolfram.com/Squarefree.htmlから

平方フリー整数を認識したり、整数の平方フリー部分を計算したりするための既知の多項式時間アルゴリズムはありません。実際、この問題は、整数因数分解の一般的な問題よりも簡単ではない場合があります（明らかに、整数を完全に因数分解できる場合、重複する因数が含まれていない限り、平方因子はありません）。代数的数体の整数環の計算は整数の平方自由部分の計算に還元できるため、この問題は数論における重要な未解決の問題です（Lenstra 1992、Pohst and Zassenhaus1997）。

于 2011-03-15T14:37:10.560 に答える
0

あなたはおそらくアトキンのふるいを調べるべきです。もちろん、これによりすべての非素数（完全な正方形だけでなく）が排除されるため、必要以上に作業が必要になる可能性があります。

于 2011-03-15T14:36:19.200 に答える
0

[n,m] などの間隔でいくつの平方自由数を計算するためのより良いアルゴリズムを見つけました。未満の素数を得ることができますsqrt(m)。次に、これらの素数の平方の倍数を引いてから、m 未満の 2 つの素数の積の倍数を足し、次に木を引いて、さらに 4 を足す必要があります....最後に、答え。確かにそれはで実行されO(sqrt(m))ます。

于 2012-09-01T02:29:20.020 に答える
0

少しグーグルで調べてみると、Jプログラムが説明されているこのページが見つかりました。複雑な構文の一部であるアルゴリズムでは、数値が平方フリーかどうかを確認できます。

  • 完全平方 PS のリストを生成し、

  • 数字 N をリスト PS の数字で割ります

  • リストに整数が 1 つしかない場合、N は平方フリーです。

好みの言語でアルゴリズムを実装し、1 から n までの任意の数で繰り返すことができます。

于 2011-03-15T15:07:25.723 に答える
0

http://www.marmet.org/louis/sqfgap/

Armenが提案したセクション「基本アルゴリズム：エラトステネスのふるい」をチェックしてください。次のセクションは「アルゴリズムの改善」です。

また、FWIW、メビウス関数、平方自由数も関係しています。

于 2011-03-15T15:35:02.570 に答える