[1,x] の範囲で n の素数を数えたいと思います。私はオイラーファイ関数を使用しようとしましたが、[1、n] を与えます。オイラーファイまたはこれを行うための他のアプローチの変更を提案できますか? phi(n) = n* (1-(1/p)) の積を使用しました。ここで、p は n の素因数です。
質問する
4074 次
1 に答える
2
包含除外原則を使用できます
N の一意の素因数を見つけます (N と X <=10^10 を考慮すると、10-12 を超えることはできません)。
これで、割るだけで、<=x で 'y' で割り切れる数を見つけることができます。y に対する n の因数のすべての組み合わせを試してください(最悪の場合、2^10 (1024) しか得られません)。ここで包含除外を使用して、x より小さい n の素数を見つけます。
ある数が n と互いに素でない場合、n と共通の素因数が少なくとも 1 つあるという考え方です。
ここの例では、X=35 と N=30 を考えてみましょう
まず、数の一意の素因数を見つけます。(それらの数は 10-12 を超えてはなりません)。N ={2,3,5} の一意の素因数。
各因子PAIRの積を求めます。{2x3、2x5、3x5 または 6、10、15}。
各因子TRIPLETの積を求めます: { 2x3x5 または 30}。
すべての因子が乗算されるまで繰り返します: {N=30 で、これ以上の手順は必要ありません}。
ステップ 1 の各係数で割った X の合計を求めます: {X=35: (35/2)+(35/3)+(35/5) = (17+11+7)=35}
STEP 2 の各数値で割った X の合計を求めます: {X=35: 35/65+3+2=10}
XをSTEP3の各数値で割った合計を求める：{X=35:1}
ステップ 4 のすべての結果が吸収されるまで繰り返します: {x=35 これ以上のステップは必要ありません}
範囲 [1..X] = X - step5 + step6 - step7 内の N に対する素数の数 {N=30、X=35 は 35 - 35 + 10 - 1 = 9 で与えられます}。
N=30、X=60 の場合、次のようになります。
60 - (60/2 + 60/3 + 60/5) + (60/6 + 60/10+ 60/15) - (60/30) = 60 - (30+20+12) + (10+6) +4) - 2 = 60 -62 + 20 - 2 = 16.
X = 10 とします。N = 6 = 2 * 3 です。
{1, 2, 3, ..., 10} という数字があります。
2 の倍数をすべて削除すると、{1, 3, 5, 7, 9} が得られます。
3 の倍数をすべて削除します。次の結果が得られます: {1, 5, 7}。
これを効率的にカウントするにはどうすればよいでしょうか。次の質問に答えてみてください: [1, X] の中に p で割り切れる数はいくつありますか? Floor(X/p)ですよね？つまり、p、2p、...、kp で、kp <= X です。したがって、X から Floor(X/p) を引くと、[1 で p と互いに素な数の数が得られます。 、 バツ]。
この例では、10 個の数字があります。2 で割り切れる数の数は 10/2、つまり 5 です。つまり、10-5 = 5 の数は 2 と素数です。同様に、3 の倍数である 10/3=3 の数があります。 2 と 3 が互いに素な 5-3=2 の数が存在することは? いいえ、二重にカウントされているためです。なんで？6 は p = 2 と 3 のカウントに含まれています。したがって、2 と 3 の倍数を加算してこれを説明する必要があります。[1, 10] には 2 と 3 の倍数は 1 つしかなく、6 です。 、 1 を足します。つまり、答えは 10 - 5 - 3 + 1 = 3 です。これは正しいです。
これを一般化したものが包含と排除の原則です。すべての n について、その素因数を見つけているだけで、10 程度未満になることは確かです。これは、素因数分解が続くエラトステネスのふるいを使用して行われます。(X < 10^9 であるため、数値が持つ素因数の最大数は少なくなります。最初の 10 個の素数の積を見つけてみてください。6469693230 になり、約 64*10^9 になります。(i最大制限を 10^10 と考えてください。これは、10^18 のような大きな数に簡単に拡張できます。)
これが役立つことを願っています!!
于 2013-06-15T08:17:22.913 に答える