质数分解分割错误，欧拉计划问题 #3

Question

我今年 16 岁，正在学习用 C++ 编写代码。有人建议我检查一些项目欧拉问题作为 class 额外内容，我真的很喜欢它们，但是我卡在了问题 3 上。任务是在我的代码中找到数字 n 的最高质因数。我研究了我的问题，valgrind 通过了代码。

 //
//  7.cpp
//  Thom's Playground
//
//  Created by Thom Foster on 25/01/2015.
//  Find the largest prime factor
//

#include <iostream>
using namespace std;

// Two Routines
//  - Find the highest factor
//  - Out of all those factors, find the highest one which is prime

int main(){

    int HPF;

// FIND THE HIGHEST FACTOR - METHOD 1
    // Initialise the number to find the HPF of , n.
    unsigned long long n = 66761275016;
    // Initialise an array to store the factors, f, with size of n+1, and f[0] is 0
    long long f[n+1];
    f[0] = 0;
    // Divide my nummber (n), by every number up to and including n, where the divisor of n is i
    for (long long i = 1 ; i <= n ; i ++){
        // After each value of i, check if the remainder of n / i is 0.
        if (n % i == 0){
            // If it is, add this to the array of factors, f, in the position f[i], where i is the state of the for loop.
            f[i] = i;
        } // End of if statement
        else {
            f[i] = 0;
        } // End of else
    } // End of for loop

// WHICH OF THOSE FACTORS IS THE HIGHEST PRIME

   for ( long long j = 1 ; j < n+1 ; j++){
       if (f[n-j+1] != 0){
           long long x = f[n-j+1];
           // Start of check prime function
                long long i = 2;
                while ( x % i != 0 && i <= x ){
                    i = i + 1;
                    }
           if (x == i) {
               cout << x << " is prime" << endl;
               return 0;
           }

                else cout << x << " was violated" << endl;
        // end of check prime function
       } // End of check factor if
   } // End of for
} // End of main

这适用于所有低于 6 位数字的数字，之后我得到一个分段错误 11。提前致谢，汤姆

Answer 1

问题是这样的：

unsigned long long n = 66761275016;
// Initialise an array to store the factors, f, with size of n+1, and f[0] is 0
long long f[n+1];

您确实无法在普通 PC 的 RAM 中分配大约 500 GiB 的堆栈 space。你必须重新考虑你的算法，不需要这个庞大的数组。

Answer 2

你不需要做所有的工作；特别是，您不需要分配所有内存。这是一个简单的算法，可以快速分解适度大小的整数，包括欧拉计划 3 的整数：

function factors(n)
    f := 2
    while f * f <= n
        while n % f == 0
            output f
            n := n / f
        f := f + 1
    if n > 1
        output n

以递增顺序输出n的质因数。它通过试验除法来工作，测试每个 f 以确定它是否是 n 的因子；当它找到一个因子时，它会输出它，然后将 n 减少为其剩余的辅因子。当f×f超过n时，不可能有剩余的素因子，所以n 是输出。

有更快的整数因式分解算法，包括试除法的其他变体。但是这个算法很简单，而且总是有效，并且在数量惊人的情况下就足够了。

祝你学习顺利。

质数分解分割错误，欧拉计划问题 #3

Prime factorisation segmentation error, for Project Euler Prob #3

c++

segmentation-fault

prime-factoring