獲取錯誤的答案項目歐拉＃27

我在C++工作項目歐拉＃27：獲取錯誤的答案項目歐拉＃27

歐拉出版了顯着的二次公式：

N²+ N + 41

它（40 + 1）+ 41可以被41整除，並且肯定是當可以將41（40 + 1）+41除以41時得到的40個素數連續值n = 0到39.然而，當n = 40,40時，40 + 40 + 41 = 。 41 = 41,412 + 41 + 41顯然可被41整除。

使用計算機，令人難以置信的公式n² - 79n + 1601發現了，它爲連續值n = 0 至79生成80個素數。係數-79和1601的乘積是-126479。

考慮形式的二次方程式：
n² + an + b, where |a| < 1000 and |b| < 1000 

where |n| is the modulus/absolute value of n 
e.g. |11| = 11 and |−4| = 4 
查找的係數，a和b的產物，爲對二次表達產生的素數爲n個連續的值的最大數目，開始用正= 0

當真實答案是-59231時，我總是收到-60939。我錯過了什麼？

#include <iostream> 
#include "Helper.h" 
using namespace std; 

int formula(int a, int b, int n) { 
    return ((n * n) + (a * n) + b); 
} 

int main() { 
    int most = 0; 
    int ansA = 0; 
    int ansB = 0; 
    bool end = false; 

    for(int a = 999; a >= -999; a--) { 
     for(int b = 999; b >= 2; b--) { //b must be prime 
      if(Helper::isPrime(b)) { 
       end = false; 
       for(int n = 0; !end; n++) { 
        if(!Helper::isPrime(formula(a, b, n))) { 
         if(n-1 > most) { 
          most = n-1; 
          ansA = a; 
          ansB = b; 
         } 
         end = true; 
        } 
       } 
      } 
     } 
    } 
    cout << ansA << " * " << ansB << " = " << ansA * ansB << " with " << most << " primes." << endl; 
    return 0; 
}

在情況下，它的問題，這裏是我的isPrime功能：

bool Helper::isPrime(int num) { 
    if(num == 2) 
     return true; 

    if(num % 2 == 0 || num == 1 || num == 0) 
     return false; 

    int root = (int) sqrt((double)num) + 1; 
    for(int i = root; i >= 2; i--) { 
     if (num % i == 0) 
      return false; 
    } 
    return true; 
}

來源

2011-07-15 paperbd

我認爲'n-1'部分是錯誤的：如果'n == 0'的答案是主要的，但1不是，那麼當你迭代一個並退出當它真的是一個時，你會說'最= 0'。這似乎不是你的其他問題的來源，但。 –

我複製了你的代碼，並用我的IsPrime在C＃中運行，得到了正確的答案。所以無論你的isPrime方法是否有缺陷，或者C++處理「公式（a，b，n）」的方式都不符合你的期望。 –

我加了我的isPrime以防萬一。 – paperbd

您允許a是負的，而你的formula返回一個int。使用負數調用Helper :: isPrime是否有意義（換句話說，Helper :: isPrime是否使用unsigned int？）

來源

2011-07-15 16:44:51

謝謝！所有我需要添加到isPrime是'if（num <0）num * = -1;' – paperbd

+1就是這樣，如果您更改OP的isPrime返回false爲負數，然後它會生成預期的答案。 –

@paperbd：你應該做的是拒絕負數作爲主要數據。第一個素數是2. –

這是我的java版本。希望它有幫助：

static int function(int n, int a, int b){ 
    return n*n + a*n + b; 
} 
static int consequitive_Primes(int a, int b, HashSet<Integer> primes){ 
    int n = 0; 
    int number = 0; 
    while(true){ 
     if(!primes.contains(function(n, a, b))) 
      break; 
     number++; 
     n++; 
    } 
    return number; 
} 
static HashSet<Integer> primes (int n){ 
    ArrayList<Integer> primes = new ArrayList<Integer>(); 
    primes.add(3); 
    for(int i=3; i<n;i+=2){ 
     boolean isPrime = true; 
     for(Integer k:primes){ 
      if(i%k==0){ 
       isPrime = false; 
       break; 
      } 
     } 
     if(isPrime) primes.add(i); 
    } 
    return new HashSet<Integer>(primes); 
} 
static long q27(){ 
    HashSet<Integer> primes = primes(1000); 
    int max = 0; 
    int max_ab = 0; 
    for(int a = -999; a<1000;a++){ 
     for(int b = -999; b<1000;b++){ 
      int prime_No = consequitive_Primes(a,b,primes); 
      if(max<prime_No){ 
       max = prime_No; 
       max_ab = a*b; 
      } 
     } 
    } 
    return max_ab; 
}

來源

2015-08-15 20:38:48

獲取錯誤的答案項目歐拉＃27

回答

相關問題