項目歐拉＃10，JAVA

可能重複：
Project Euler, Problem 10 java solution not working 項目歐拉＃10，JAVA

所以，我試圖解決Project Euler Problem 10在Java中，和我得到不正確的答案。這裏是我的代碼：

public class Problem10 { 
public static void main(String[] args) 
{ 
    long sum =0; 
    for(int i =3;i<2000000;i+=2) 
    { 
     if(isPrime(i)) 
     { 
      sum+=i; 
     } 
    } 
    System.out.println(sum); 
} 

public static boolean isPrime(int n) 
{ 
    boolean prime = true; 
    if (n<2) return false; 
    if (n==2) return true; 
    if (n%2==0) return false; 
    for (int i = 3; i<=Math.sqrt(n);i+=2) 
    { 
     if (n%i==0) 
     { 
      prime=false; 
      break; 
     } 
    } 
    return prime; 
} 
}

哪打印出142913828920，哪個項目歐拉告訴我是錯誤的。

任何想法？

（另外，我知道我的尋找素數的方法是非常低效的。）

來源

2010-08-03 Colin DeClue

http://projecteuler.net/index.php?section=problems&id=10 – Isaac 2010-08-03 18:19:41

這種方法不是非常* *低效率的。在Haskell中它是'2：[n |所有（（> 0）.rem n）[3,5..floor（sqrt（fromIntegral n））]] - - 奇數的最小嚐試除法。下面的*非常低效，*流行*：'sieve [2 ..]其中sieve（x：xs）= x：sieve [n | n < - xs，rem n x> 0]' - 質數過多的試劃。更慢也更受歡迎的是'[n |所有（（> 0）.rem n）[2..n-1]] - 所有數字的過度試劃。 '[n | n < - [2 ..]，而不是$ elem n [j * k | j < - [1..n-1]，k < - [1..n-1]]]'是冠軍 - 我看到了它（在Java IIRC中）！ – 2012-06-16 08:05:24

for(int i =3;i<2000000;i+=2)

2是一個素數。

來源

2010-08-03 18:17:53 dcp

如果你會注意到上面，我有if（n == 2）返回true; – 2010-08-03 18:18:51

但主要的是，你的循環從3開始。 – dcp 2010-08-03 18:19:26

但是你從3開始，所以n永遠不會等於2 – 2010-08-03 18:20:35

您可以通過僅分開素數來加速您的代碼。例如，你可以知道35不是一個質數，只是試圖將它除以2，3，5.不需要嘗試4.技巧是，任何時候當你找到一個素數時，將它保存在一個列表中或者一個向量。在你的isPrime函數中，只需迭代列表直到它碰到sqrt（n）而不是3..sqrt（n）之間的每個值。

來源

2010-08-08 22:19:57 dgg32

這會佔用大量內存 – 2010-08-08 22:29:18

@amir：不是真的......有150000個素數在200萬以下，而且他們會越來越稀少。使用32位整數列表，只需要600kb。 – Ponkadoodle 2010-08-08 22:44:36

在任何情況下，代碼只需不到5秒即可按原樣運行。不需要優化，真的。 – 2010-08-09 12:51:51

您可以使用Sieve進一步加速您的代碼。

來源

2010-08-08 23:46:45 Kizaru

我發現以下方法非常有效，當我檢查一個數字是否是素數時，我只將數字除以先前找到的素數並且低於n的平方根。不需要檢查n的平方根以下的所有數字。它只需要一秒鐘以上！

public class Problem10 { 

    private static List<Long> listOfPrimes = new ArrayList<Long>(); 

    public static void main(String args[]) { 

     long count = 0; 
     for (long i = 2; i < 2000000; i++) { 
      if (isPrime(i)) { 
       count += i; 
       System.out.print(i + " "); 
      } 
      if (i % 1000 == 0) { 
       System.out.println(); 
      } 
     } 

     System.out.println("\nTotal " + count); 

    } 

    private static boolean isPrime(long n) { 

     String strFromN = new Long(n).toString(); 
     if ((strFromN.length() != 1) && (strFromN.endsWith("2") || strFromN.endsWith("4") || strFromN.endsWith("5") || strFromN.endsWith("6") || strFromN.endsWith("8"))) { 
      return false; 
     } 

     for (Long num : listOfPrimes) { 
      if (num > Math.sqrt(n)) { 
       break; 
      } 
      if (n % num.longValue() == 0) { 
       return false; 
      } 
     } 


     listOfPrimes.add(new Long(n)); 
     return true; 
    } 
}

來源

2012-06-15 08:58:34 web2dev

無需測試2以上的偶數;它已經被稱爲prime：替換'long count = 0; for（long i = 2; i <2000000; i ++）{'with'long count = 2; for（long i = 3; i <2000000; i + = 2）{'。所以現在不需要字符串轉換。 – 2012-06-16 08:14:35

項目歐拉＃10，JAVA

回答

相關問題