我需要一个最优算法来找到数字N的最大除数。最好是在C ++或C＃中
我目前正在使用以下代码，但它对于大数字来说非常慢
static int divisor(int number) { int i; for (i = number / 2; i >= 1; i--) { if (number % i == 0) { break; } } return i; } 首先想到你可以找到最小的除数d（当然不等于1），那么N / d将是你正在寻找的最大除数。
例如，如果N可以被3整除，那么你将需要2次迭代来找到答案 – 在你的情况下，它将是大约N / 6次迭代。
编辑：为了进一步改进你的算法，你可以只迭代奇数（在检查你的数字是否为偶数之后），或者更好的是，如果你有预先计算的素数列表，那么你可以迭代它们只是因为最小的除数很明显是素数。
一个巨大的优化（不确定它是否完全最优 – 你必须向数学家询问）是仅使用素数向上搜索。 正如Vladimir和Bunnit所说，向上搜索会更好，因为你会发现它要快得多。 然后，返回反转（ number / i ）。 但是，如果你已经尝试了2并且干了，那么尝试4或6是没有意义的。同样，如果你尝试过3，那么尝试6或9是没有意义的。
因此，如果运行时间是一个很大的问题，那么您可以获得程序中硬编码的前100个素数列表。 测试每一个。 如果到那时你没有找到答案，那么你可以增加2（跳过偶数）。
查找大数因子的行业标准方法之一是Quadratic Sieve算法。
读一读：
http://en.wikipedia.org/wiki/Quadratic_sieve
PS你还应该考虑你的数字有多大。 不同的因子分解算法倾向于在特定大小上表现良好，而对其他因素则不然。 如QS wiki文章中所述，对于小于约100个十进制数字的数字，此方法通常是最快的。
不知道它是否是最佳解决方案，但你可能会更好，从2开始然后向上，例如：
static int divisor(int number) { int i; for (i = 2; i
编辑
让它与素数一起工作：
static int divisor(int number) { int i; for (i = 2; i <=sqrt(number); i++) { if (number % i == 0) { return number/i; } } return 1; }
优化：奇数不能将偶数作为最大除数。 尽早使用此filter编号。 所以，如果给出奇数。
-
首先用2来划分。
-
然后每次在循环中将i递减2
这将改善奇数的速度。
为了限制您的搜索空间，您应该从2开始，然后处理该数字的平方根。 有统计学上说，有更多的数字（在有限的搜索空间中）被2整除，而不是27，所以你更有可能获得低除数而不是高除数。
当您处理（例如）1,000,000时，使用平方根而不是值的一半时会发现很大的差异。 区别在于您的方法的搜索空间为500,000，而平方根方法的搜索空间为1,000。
另一个优点是通过折扣两倍的倍数将正面的搜索空间减半。 然后，当你有最低的除数时，最高的除数就是数除以该数。
伪代码：
if n % 2 == 0: # Halve search space straight up. print n / 2 else: i = 3 # Start at 3. while i * i <= n: # Or use i <= sqrt(n), provided sqrt is calc'ed once if n % i == 0: print n / i # If multiple, get opposite number, print and stop break i = i + 2 # Only need to process odd numbers
找到第一个除数N的素数。假设素数是p。 将N除以d。 这是您想要的结果。
你基本上已经遇到了“大数分解”问题，这是当今公钥加密的基础，并且已知（或希望）是计算上难以解决的问题。 我确实希望你找不到更好的解决方案，否则全世界的整个安全基础设施都会崩溃…… 🙂
看看这里： – http://programmingpraxis.com/contents/themes/#Prime%20Numbers
编程Praxis定期为人们设置编程挑战，以便在周五午餐时间获得一些乐趣。 这个特殊的问题出现了很多，并且有几种众所周知的算法用于解决它用代码说明。
一些额外的优化：
1. If even then divisable by 2. 2. If the sum of the digits is divisable by 3, then number is divisble by 3 (ie 78 = 7 + 8 = 15 = 1 + 5 = 6 which is divisable by 3) 3. If it ends in 0 or 5 it is divisable by 5
戈登。
最好的算法取决于你的数字实际有多大。
这个问题基本上和分解整数一样难 – 如果有一些因子分解算法，使用它来构造最大的非平凡除数是相当容易的。 同样，你为数字采用的所有已知因子算法中的哪一个应该取决于它的“巨大”，对于不同的尺度，这些花哨的算法可能会有不同的性能。
您可能会在密码学，算法和计算数论的好书中找到几个（可能是不同的）答案。
同样，根据你的规模，甚至可以选择简单地预先计算一个大数字列表的素数，保存它，然后在这个列表中给出一个输入数字搜索最小的除数 – 这将立即弹出最大的除数也是。