查找第一个大于 N 且与 M 互质的数

发布于 2025-01-01 16:08:42 字数 929 浏览 1 评论 0原文

基本上，标题说明了一切。数字不太大（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) 更精确的答案。

原文

Basically, the title says everything. The numbers are not too big (the maximum for N is ~2/3 * max(long) and max M is max(long)), so I think even a simple solution that I currently have is sufficient. M is always bigger than N.

What I currently have:

Most simple, just start from N + 1, perform plain Euclidean GCD, and if it returns 1 we are done, if not increment and try again.

I would like to know what is the worst case scenario with this solution. Performance is not a big issue, but still I feel like there must be a better way.

Thanks.

About the worst case, I made a small test:

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;
        }

It is running for ~30 minutes and the worst case so far is 29 iterations. So I believe that there is a more precise answer then O(N).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

深爱成瘾 2025-01-08 16:08:42

我不知道最坏的情况，但使用 M < 的事实2⁶⁴，我可以将其限制在上面 292 次迭代和下面 53 次（消除了比率 N/M 近似固定的限制）。

令 p₁, …, 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。的上限Σ_i=1,…,k ceil(49/p_i) 是 Σ_i=3,…,16 ceil(49/q _i) = 48，其中 q 是从 q₁ = 2 开始的素数。（这是因为 ∏_{i=3,…,17≥ 2⁶⁴ 意味着 M 是除 2 和 3 之外最多 14 个不同素数的乘积。）我们得出的结论是，至少有一个提到的整数与 M 互质。}

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

我预计这两个界限都可以在不需要太多工作的情况下得到改善，尽管我不清楚目的是什么。对于上限，单独处理 2 和 3 都是 M 的约数的情况，因为这样 M 最多可以是13个其他素数的乘积。对于下界，可以尝试通过运行埃拉托色尼筛来计算一系列整数除以这些整数的素数列表，从而找到一个好的 M。然后在范围内扫一个窗口；如果窗口中不同素数的乘积太大，则将窗口的尾端提前；否则，将前端提前。