4

基本的にタイトルが全てです。数値が大きすぎない (N の最大値は ~2/3 * max(long) で、最大 M は max(long) です) ので、現在持っている単純なソリューションでも十分だと思います。M は常に N より大きくなります。

私が現在持っているもの：

  • 最も単純なのは、N + 1 から始めて、単純なユークリッド GCD を実行し、1 が返された場合は完了です。そうでない場合は、インクリメントして再試行します。

このソリューションの最悪のシナリオを知りたいです。パフォーマンスは大きな問題ではありませんが、それでももっと良い方法があるはずだと感じています。

ありがとう。

最悪のケースについて、私は小さなテストを行いました：

Random r = new Random();
while (true)
            {
                long num = (long) r.Next();
                num *= r.Next();
                f((long)(num * 0.61), num);
            }

...

public static int max;

        public static int f(long N, long M)
        {
            int iter = 0;
            while (GCD(N++, M) != 1)
            {
                iter++;
            }

            if (iter > max)
            {
                max = iter;
                Console.WriteLine(max);
            }

            return 0;
        }

約 30 分間実行され、これまでの最悪のケースは 29 回の反復です。したがって、O(N) よりも正確な答えがあると思います。

4

2 に答える 2

4

最悪のシナリオはわかりませんが、M <2 64であるという事実を使用して、上で292回、下で53回制限できます（比率N / Mがほぼ固定されるという制限がなくなります）。

p 1、…、p kを、Mが割り切れる5以上の素数とします。N'≥Nを、N' = 1mod6またはN'=5mod6となる最小の整数とします。各i=1、…、kについて、素数piは最大でceil（49 / p i）を除算します。整数N'、N' + 6、N'+ 12、…、N' +288。∑ <sub> i = 1、…、k ceil（49 / p i）の上限は∑<sub>iです。 = 3、…、16ceil（49 / q i ）= 48、ここでqはq 1 = 2で始まる順序の素数です（これは、∏ <sub> i = 3、…、17≥264は次のことを意味するためです。 Mは、2と3以外の最大14個の異なる素数の積です。）上記の整数の少なくとも1つは、Mに対して比較的素数であると結論付けます。

下限については、M = 614889782588491410（最初の15個の素数の積）とし、N = 1とします。1の後、最初の15個の素数に対して互いに素な最初の整数は16番目の素数53です。

どのような目的であるかはわかりませんが、あまり手間をかけずに両方の限界を改善できると思います。上限については、2と3が両方ともMの約数である場合を別々に処理します。その場合、Mは最大で13個の他の素数の積になる可能性があります。下限については、エラトステネスのふるいを実行して、整数の範囲について、それらの整数を分割する素数のリストを計算することにより、適切なMを見つけようとすることができます。次に、範囲全体でウィンドウをスイープします。ウィンドウ内の個別の素数の積が大きすぎる場合は、ウィンドウの後端を進めます。それ以外の場合は、リーディングエンドを進めます。

于 2012-02-01T15:26:07.733 に答える
1

確かにそれは O(n) ではありません。素数のギャップが log e n であることを知ることで、単純にアルゴリズムが最大で log n の反復を持っていると言うことができます (最大で log e nの数を渡した後、新しい素数が表示されるためです。指定された数に対する素数) このギャップの詳細については、素数のギャップを参照してください。n

したがって、境界のあるケースでは、log e n = log e 2 64 <= 44 よりも小さく、44反復よりも小さくなります。

于 2012-02-01T17:31:22.533 に答える