我需要一个优化算法寻找一个数N preferably在C ++或C＃的最大除数 [英] I need an optimal algorithm to find the largest divisor of a number N. Preferably in C++ or C#

问题描述

我目前使用下面的code，但其大量的非常慢

 

        静态INT除数（INT数）
        {
            INT I;
            对于（I =号/ 2; I> = 1;我 - ）
            {
                如果（编号％我== 0）
                {
                    打破;
                }
            }
            返回我;
        }
 

解决方案

首先想到的，你可以找到的最小除数D（不等于1个疗程），那么N / D将是您正在寻找的最大除数。

例如，如果N是被3整除，那么你就需要2次迭代中找到了答案 - 在您的情况这将是大约N / 6次迭代。

编辑：：要进一步提高你的算法，你只能通过奇数迭代（检查后，如果您个数为偶数），或者甚至更好，如果你有一个素数pre-名单计算的话，你可以遍历它们只是因为最小除数，显然是一个素数。

I am currently using the following code but its very slow for large numbers

        static int divisor(int number)
        {
            int i;
            for (i = number / 2; i >= 1; i--)
            {
                if (number % i == 0)
                {
                    break;
                }
            }
            return i;
        }

解决方案

First thought you can find the smallest divisor d (not equal to 1 of course), then N/d will be the largest divisor you're looking for.

For example if N is divisible by 3 then you'll need 2 iterations to find the answer - in your case it would be about N/6 iterations.

Edit: To further improve your algorithm you can iterate through odd numbers only (after checking if you number is even) or, even better, if you have the list of primes pre-calculated then you can iterate through them only because smallest divisor is obviously is a prime number.

这篇关于我需要一个优化算法寻找一个数N preferably在C ++或C＃的最大除数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！