C++ 寻找主要因素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11924249/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding prime factors
提问by Bob John
#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);
}
I'm trying to find the prime factors of the number 600851475143 specified by Problem 3on Project Euler (it asks for the highest prime factor, but I want to find all of them). However, when I try to run this program I don't get any results. Does it have to do with how long my program is taking for such a large number, or even with the number itself?
我试图找到 欧拉项目中问题 3指定的数字 600851475143的质因数（它要求最高的质因数，但我想找到所有这些）。但是，当我尝试运行这个程序时，我没有得到任何结果。它是否与我的程序为如此大的数字花费的时间有关，甚至与数字本身有关？
Also, what are some more efficient methods to solve this problem, and do you have any tips as to how can I steer towards these more elegant solutions as I'm working a problem out?
另外，有什么更有效的方法可以解决这个问题，你有什么建议可以让我在解决问题时转向这些更优雅的解决方案吗？
As always, thank you!
一如既往，谢谢！
回答by user448810
Your algorithm is wrong; you don't need i. Here's pseudocode for integer factorization by trial division:
你的算法是错误的；你不需要我。这是通过试除进行整数分解的伪代码：
define factors(n)
z = 2
while (z * z <= n)
if (n % z == 0)
output z
n /= z
else
z++
if n > 1
output n
I'll leave it to you to translate to C++ with the appropriate integer datatypes.
我将把它留给您使用适当的整数数据类型转换为 C++。
Edit: Fixed comparison (thanks, Harold) and added discussion for Bob John:
编辑：固定比较（谢谢，哈罗德）并添加了对鲍勃约翰的讨论：
The easiest way to understand this is by an example. Consider the factorization of n = 13195. Initially z = 2, but dividing 13195 by 2 leaves a remainder of 1, so the else clause sets z = 3 and we loop. Now n is not divisible by 3, or by 4, but when z = 5 the remainder when dividing 13195 by 5 is zero, so output 5 and divide 13195 by 5 so n = 2639 and z = 5 is unchanged. Now the new n = 2639 is not divisible by 5 or 6, but is divisible by 7, so output 7 and set n = 2639 / 7 = 377. Now we continue with z = 7, and that leaves a remainder, as does division by 8, and 9, and 10, and 11, and 12, but 377 / 13 = 29 with no remainder, so output 13 and set n = 29. At this point z = 13, and z * z = 169, which is larger than 29, so 29 is prime and is the final factor of 13195, so output 29. The complete factorization is 5 * 7 * 13 * 29 = 13195.
理解这一点的最简单方法是通过一个例子。考虑 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、9、10、11、12，但 377 / 13 = 29 没有余数，所以输出 13 并设置 n = 29。此时 z = 13，z * z = 169，即大于 29，所以 29 是素数，是 13195 的最终因数，所以输出 29。完全因式分解为 5 * 7 * 13 * 29 = 13195。
There are better algorithms for factoring integers using trial division, and even more powerful algorithms for factoring integers that use techniques other than trial division, but the algorithm shown above will get you started, and is sufficient for Project Euler #3. When you're ready for more, look here.
有使用试除法分解整数的更好算法，甚至使用试除法以外的技术分解整数的更强大算法，但上面显示的算法将帮助您入门，并且足以用于 Project Euler #3。当您准备好了解更多信息时，请看这里。
回答by huseyin tugrul buyukisik
600851475143 is outside of the range of an int
600851475143 超出了 int 的范围
void whosprime(int x) //<-----fix heere ok?
{
bool imPrime = true;
for(int i = 1; i <= x; i++)
{...
...
回答by Chris Koknat
A C++ implementation using @user448810's pseudocode:
使用@user448810 的伪代码的 C++ 实现：
#include <iostream>
using namespace std;
void factors(long long n) {
long long z = 2;
while (z * z <= n) {
if (n % z == 0) {
cout << z << endl;
n /= z;
} else {
z++;
}
}
if (n > 1) {
cout << n << endl;
}
}
int main(int argc, char *argv[]) {
long long r = atoll(argv[1]);
factors(r);
}
// g++ factors.cpp -o factors ; factors 600851475143
Perl implementation with the same algorithm is below.
Runs ~10-15x slower (Perl 0.01 seconds for n=600851475143)
下面是具有相同算法的 Perl 实现。
运行速度慢约 10-15 倍（n=600851475143 时 Perl 0.01 秒）
#!/usr/bin/perl
use warnings;
use strict;
sub factors {
my $n = shift;
my $z = 2;
while ($z * $z <= $n) {
if ( $n % $z ) {
$z++;
} else {
print "$z\n";
$n /= $z;
}
}
if ( $n > 1 ) {
print "$n\n"
}
}
factors(shift);
# factors 600851475143
回答by s.n
Here is my code that worked pretty well to find the largest prime factor of any number:
这是我的代码，可以很好地找到任何数字的最大素因数：
#include <iostream>
using namespace std;
// --> is_prime <--
// Determines if the integer accepted is prime or not
bool is_prime(int n){
int i,count=0;
if(n==1 || n==2)
return true;
if(n%2==0)
return false;
for(i=1;i<=n;i++){
if(n%i==0)
count++;
}
if(count==2)
return true;
else
return false;
}
// --> nextPrime <--
// Finds and returns the next prime number
int nextPrime(int prime){
bool a = false;
while (a == false){
prime++;
if (is_prime(prime))
a = true;
}
return prime;
}
// ----- M A I N ------
int main(){
int value = 13195;
int prime = 2;
bool done = false;
while (done == false){
if (value%prime == 0){
value = value/prime;
if (is_prime(value)){
done = true;
}
} else {
prime = nextPrime(prime);
}
}
cout << "Largest prime factor: " << value << endl;
}
Keep in mind that if you want to find the largest prime factor of extremely large number, you have to use 'long' variable type instead of 'int' and tweak the algorithm to process faster.
请记住，如果您想找到极大数的最大质因数，则必须使用“long”变量类型而不是“int”并调整算法以加快处理速度。
回答by Serge Voloshenko
short and clear vesion:
简短而清晰的版本：
int main()
{
int MAX = 13195;
for (int i = 2; i <= MAX; i++)
{
while (MAX % i == 0)
{
MAX /= i;
cout << i << ", " << flush; // display only prime factors
}
return 0;
}
回答by Iqra.
This is one of the easiest and simple-to-understand solutions of your question. It might not be efficient like other solutions provided above but yes for those who are the beginner like me.
这是您问题的最简单易懂的解决方案之一。它可能不像上面提供的其他解决方案那样高效，但对于像我这样的初学者来说是的。
int main() {
int num = 0;
cout <<"Enter number\n";
cin >> num;
int fac = 2;
while (num > 1) {
if (num % fac == 0) {
cout << fac<<endl;
num=num / fac;
}
else fac++;
}
return 0;
}
}
回答by sakib_akon
# include <stdio.h>
# include <math.h>
void primeFactors(int n)
{
while (n%2 == 0)
{
printf("%d ", 2);
n = n/2;
}
for (int i = 3; i <= sqrt(n); i = i+2)
{
while (n%i == 0)
{
printf("%d ", i);
n = n/i;
}
}
if (n > 2)
printf ("%d ", n);
}
int main()
{
int n = 315;
primeFactors(n);
return 0;
}
回答by rashedcs
Simple way :
简单的方法：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll largeFactor(ll n)
{
ll ma=0;
for(ll i=2; i*i<=n; i++)
{
while(n%i == 0)
{
n=n/i;
ma=i;
}
}
ma = max(ma, n);
return ma;
}
int main()
{
ll n;
cin>>n;
cout<<largeFactor(n)<<endl;
return 0;
}
Implementation using prime sieve ideone.
使用prime筛选ideone实现。
回答by Aayush Ghosh
Since 600851475143 is out of scope for int as well as single long type wont work here hence here to solve we have to define our own type here with the help of typedef. Now the range of ll is some what around 9,223,372,036,854,775,807.
由于 600851475143 超出了 int 的范围，并且单个 long 类型在这里不起作用，因此在这里要解决我们必须在 typedef 的帮助下在这里定义我们自己的类型。现在 ll 的范围大约是 9,223,372,036,854,775,807。
typedef long long int LL
typedef long long int LL
回答by Steve Jessop
Edit: I'm wrong (see comments). I would have deleted, but the way in which I'm wrong has helped indicate what specifically in the program takes so long to produce output, so I'll leave it :-)
编辑：我错了（见评论）。我会删除，但我错的方式有助于表明程序中的具体内容需要很长时间才能产生输出，所以我会留下它:-)
This program should immediately print 1(I'm not going to enter a debate whether that's prime or not, it's just what your program does). So if you're seeing nothing then the problem isn't execution speed, there muse be some issue with the way you're running the program.
这个程序应该立即打印1（我不打算讨论这是否是素数，这只是你的程序所做的）。因此，如果您什么也没看到，那么问题不在于执行速度，那么您运行程序的方式一定有问题。
