4

基本上，标题说明了一切。这些数字并不太大（N 的最大值为 ~2/3 * max(long)，max 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是大于或等于 5 且 M 可被整除的素数。令 N' ≥ N 为满足 N' = 1 mod 6 或 N' = 5 mod 6 的最小整数。对于每个 i = 1, ..., k，质数 p i最多可除 ceil(49/p i )整数 N', N' + 6, N' + 12, ..., N' + 288。 ∑<sub>i=1,...,k ceil(49/ pi ) 的上界是 ∑<sub>i =3,…,16 ceil(49/q i ) = 48，其中 q 是从 q 1 = 2开始的素数。（这是因为 ∏<sub>i=3,…,17 ≥ 2 64意味着M 是除 2 和 3 之外的最多 14 个不同素数的乘积。）我们得出结论，至少有一个所提到的整数与 M 互质。

对于下界，令 M = 614889782588491410（前十五个素数的乘积）并令 N = 1。在 1 之后，与前十五个素数相对素数的第一个整数是第十六个素数 53。

我希望这两个界限都可以在没有太多工作的情况下得到改善，尽管我不清楚目的是什么。对于上界，分别处理 2 和 3 都是 M 的除数的情况，因为 M 最多可以是其他13个素数的乘积。对于下界，可以通过运行 Eratosthenes 的筛子来尝试找到一个好的 M，以针对一系列整数计算除以这些整数的素数列表。然后在范围内扫过一个窗口；如果窗口中不同素数的乘积太大，则推进窗口的尾端；否则，推进前端。

于 2012-02-01T15:26:07.733 回答
1

当然不是 O(n)，通过知道素数间隙是 log e n，我们可以简单地说您的算法最多有 log e n 次迭代，（因为在通过最多 log e n 数后，您将看到新的素数，即对给定数字的主要尊重n）有关此差距的更多详细信息，您可以查看素数差距。

因此，对于您的有界情况，它小于 log e n = log e 2 64 <= 44 并且它将小于44迭代。

于 2012-02-01T17:31:22.533 回答