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

我试图找到欧拉项目中问题 3指定的数字 600851475143 的素因数（它要求最高的素因数，但我想找到所有这些素数）。但是，当我尝试运行这个程序时，我没有得到任何结果。这是否与我的程序需要多长时间才能处理这么大的数字，甚至与数字本身有关？

另外，有什么更有效的方法可以解决这个问题，你有什么提示可以帮助我在解决问题时转向这些更优雅的解决方案吗？

一如既往，谢谢！

4

12 回答 12

28

你的算法是错误的；你不需要我。这是通过试除法进行整数分解的伪代码：

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、9、10、11、12，但 377 / 13 = 29 没有余数，所以输出 13 并设置 n = 29。此时 z = 13，且 z * z = 169，即大于 29，所以 29 是素数，是 13195 的最终因数，所以输出 29。完整的因式分解为 5 * 7 * 13 * 29 = 13195。

有更好的整数因式分解算法使用试除法，甚至更强大的整数分解算法使用除试除法以外的技术，但上面显示的算法将帮助您入门，并且对于 Project Euler #3 来说已经足够了。当您准备好更多时，请看这里。

于 2012-08-12T17:38:06.270 回答
4

使用@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 实现。
运行速度慢约 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
于 2015-10-29T18:15:07.987 回答
3

600851475143 超出 int 范围

void whosprime(int x) //<-----fix heere ok?
{
    bool imPrime = true;

    for(int i = 1; i <= x; i++)
    {... 
      ...
于 2012-08-12T17:31:19.723 回答
0

编辑：我错了（见评论）。我会删除，但我错的方式有助于表明程序中具体的内容需要很长时间才能产生输出，所以我会留下它:-)

这个程序应该立即打印出来1（我不打算讨论它是否是素数，这正是你的程序所做的）。因此，如果您什么也没看到，那么问题不在于执行速度，那么您运行程序的方式可能存在一些问题。

于 2012-08-12T17:43:26.397 回答
0

试试下面的代码：

counter = sqrt(n)
i = 2;

while (i <= counter)
    if (n % i == 0)
        output i
    else
        i++
于 2012-08-12T17:44:00.397 回答
0

由于 600851475143 超出了 int 的范围，并且单个 long 类型在这里不起作用，因此在这里解决我们必须在 typedef 的帮助下在这里定义自己的类型。现在 ll 的范围大约是 9,223,372,036,854,775,807。

typedef long long int LL

于 2018-12-06T15:06:48.583 回答
0 
# 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;
}
于 2017-09-13T11:21:35.667 回答
0

简短而清晰的版本：

    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;
    }
于 2016-07-20T20:41:09.090 回答
0

这是我的代码，可以很好地找到任何数字的最大素数：

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

请记住，如果您想找到极大数的最大素数，您必须使用“long”变量类型而不是“int”并调整算法以更快地处理。

于 2016-06-15T07:42:05.537 回答
0

这是您问题的最简单易懂的解决方案之一。它可能不像上面提供的其他解决方案那样有效，但对于像我这样的初学者来说可以。

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;

}

于 2017-05-24T09:54:23.900 回答
0

简单的方法：

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

使用素筛ideone实现。

于 2018-09-13T08:59:52.960 回答
-2

试试这个代码。绝对是最好和最有效的：

long long number;
bool isRepetitive;

for (int i = 2; i <= number; i++) {
    isRepetitive = false;
    while (number % i == 0) {
        if(!isRepetitive){
            cout << i << endl;
            isRepetitive = true;
        }
        number /= i;
    }
}

享受！☻</p>

于 2015-10-29T16:59:21.983 回答