#include <iostream>
using namespace std;
void whosprime(long long x)
{
bool imPrime = true;
for(int i = 1; i <= x; i++)
{
for(int z = 2; z <= x; z++)
{
if((i != z) && (i%z == 0))
{
imPrime = false;
break;
}
}
if(imPrime && x%i == 0)
cout << i << endl;
imPrime = true;
}
}
int main()
{
long long r = 600851475143LL;
whosprime(r);
}
我试图找到由 Problem 3 指定的数字 600851475143 的质因数在 Project Euler 上(它要求最高素数,但我想找到所有素数)。但是,当我尝试运行这个程序时,我没有得到任何结果。它是否与我的程序处理如此大的数字所花费的时间有关,甚至与数字本身有关?
另外,有什么更有效的方法可以解决这个问题?对于我在解决问题时如何转向这些更优雅的解决方案,您有什么建议吗?
一如既往,谢谢!
最佳答案
你的算法是错误的;你不需要我。这是通过试验除法进行整数分解的伪代码:
define factors(n)
z = 2
while (z * z <= n)
if (n % z == 0)
output z
n /= z
else
z++
if n > 1
output n
我会留给您使用适当的整数数据类型转换为 C++。
编辑:修复了比较(谢谢,Harold)并添加了对 Bob John 的讨论:
理解这一点的最简单方法是通过示例。考虑 n = 13195 的因式分解。最初 z = 2,但 13195 除以 2 的余数为 1,因此 else 子句设置 z = 3 并循环。现在 n 不能被 3 或 4 整除,但当 z = 5 时,13195 除以 5 的余数为零,因此输出 5 并将 13195 除以 5,因此 n = 2639 且 z = 5 不变。现在新的 n = 2639 不能被 5 或 6 整除,但可以被 7 整除,所以输出 7 并设置 n = 2639/7 = 377。现在我们继续 z = 7,这留下了余数,除法也是如此8, and 9, and 10, and 11, and 12, but 377/13 = 29 没有余数,所以输出13,设n = 29。此时z = 13, and z * z = 169, 即大于 29,所以 29 是素数,是 13195 的最终因子,所以输出 29。完全分解为 5 * 7 * 13 * 29 = 13195。
使用试除法分解整数有更好的算法,使用试除法以外的技术分解整数的算法甚至更强大,但上面显示的算法将帮助您入门,并且足以满足欧拉计划 #3 的要求。当您准备好获取更多信息时,请查看 here .
关于c++ - 寻找主要因素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11924249/