對於歐拉項目50的錯誤答案

Question

我在嘗試歐拉項目的問題50。

的首要41，可以寫爲六個連續的素數的總和：

41 = 2 + 3 + 5 + 7 + 11 + 13這是連續 質數的最長總和，增加了低於一百的素數。 連續質數低於1000的連續素數加上素數，包含 21項，並且等於953.哪一個素數低於100萬，可以是 寫成最連續的素數之和？

這裏是我的代碼：

public class consPrime 
    { 
     static int checker(int ar[],int num,int index) //returns no.of consecutive 
     {            //primes for the given num 
      while(true) 
     { 

     int temp=num; 

     for(int i=index;i>=0;i--) 
     { 
      temp=temp-ar[i]; 

      if(temp==0) 
      { 
       return (index-i+1); 
      }    
     }   
     index--; 
     if(index==0) 
     return 0;   
     } 
    } 

    public static void main(String args[]) 
    {    
     int n=100000; 
     int ar[]=new int[n]; 
     int total=0;int flag; 

     for(int i=2;i<1000000;i++) //Generates an array of primes below 1 million 
     { 
      flag=1; 

      for(int j=2;j<=Math.sqrt(i);j++) 
      { 
       if(i%j==0) 
       { 
        flag=0; 
        break; 
       }     
      } 
      if(flag==1) 
      { 
       ar[total]=i; 
       total++; 
      }    
     } 

     int m=0; 
     int Big=0; 

     for(int i=total;i>=0;i--) //Prints the current answer with no.of prime 
     { 
      m=checker(ar,ar[i],i-1); 
      if(Big<=m) 
      {Big=m; 
       System.out.println(ar[i]+"  "+Big); 
      } 
     }   
    }  
} 

基本上它只是創建所有素數達1000000的載體中，然後通過他們找到循環的正確答案。答案是997651，計數應該是543，但我的程序分別輸出990707和75175。什麼可能是錯的？

Answer 1

幾大問題：

1. 一些小問題，第一：學會正確的縮進你的代碼，學會用正確的命名約定。在Java中，變量名稱使用camelCasing，而類型名稱使用PascalCasing。

2. 您的邏輯中存在很多問題：通過質數數組循環，直到您達到零或直到循環遍歷數組中的所有數字爲止。但是，請注意，整數有下溢/溢出。 「臨時」可能會繼續扣除並變爲負值，並變爲正值，然後等到零並達到零。但這不是正確答案

3. 您只試圖找到以索引-1結束的連續數字。例如，要檢查索引10處的質數，您會從索引9向後找到連續質數。然而，連續的總數達到你的目標數很少（事實上幾乎從不，除了5）包含「前一個」素數。整個邏輯完全錯誤。

4. 何況你通過了檢查，這是由用戶@ PM-77-1

Answer 2

這裏的評論中提及了不正確的參數是另一種方法是採用43毫秒。

它是基於以下的方法：

1）< = 1000000是使用篩子

2生成的素數）它循環在爲O（n ）通過所有數字和它計算連續的素數。第一個循環會更改序列的第一個元素，第二個循環會從該位置開始的元素並將它們添加到總和中。如果總和爲素數並且它包含最大數量的素數，則它保存在變量中。

import java.util.ArrayList; 
import java.util.List; 

public class P50 { 

    private final static int N = 1_000_000; 

    public static void main(String[] args) { 
     boolean primes[] = generatePrimes(N); 
     List<Integer> primeIntegers = new ArrayList<Integer>(); 
     for (int i = 0; i < primes.length; i++) { 
      if (primes[i]) { 
       primeIntegers.add(i); 
      } 
     } 
     int count = 0; 
     int sum = 0; 
     int finalSum = 0; 
     int finalCount = 0; 
     int totalPrimes = primeIntegers.size(); 
     for (int start = 0; start < totalPrimes; start++) { 
      sum = 0; 
      count = 0; 
      for (int current = start; current < totalPrimes; current++) { 
       int actual = primeIntegers.get(current); 
       sum += actual; 
       if (sum >= N) { 
        break; 
       } 
       if (primes[sum]) { 
        if (count > finalCount) { 
         finalCount = count; 
         finalSum = sum; 
        } 
       } 
       count++; 
      } 
     } 
     System.out.println(finalSum); 
    } 

    private static boolean[] generatePrimes(int n) { 
     boolean primes[] = new boolean[n]; 
     for (int i = 0; i < n; i++) { 
      primes[i] = true; 
     } 
     primes[0] = false; 
     primes[1] = false; 
     // i = step 
     for (int i = 2; i * i < n; i++) { 
      if (primes[i]) { 
       for (int j = i * i; j < n; j += i) { 
        primes[j] = false; 
       } 
      } 
     } 
     return primes; 
    } 

}