計算素數直到N

此代碼可以正常計數直到n的素數。問題是當n值大到1000000或更多時，那麼執行和打印輸出需要很長時間（超過30秒）。我想解決這個問題。任何幫助都會很棒。 下面是代碼：計算素數直到N

public class PrimeNotillN { 

     public static void main(String[] args) { 

      int n = 1000; 
      int count = 0; 

      for (int i = 2; i < n; i++) { 
       boolean res = checkprime(i); 
       if (res == true) 
        count++; 
      } 
      System.out.println("total prime number till " + n + " is " + count); 
     } 

     private static boolean checkprime(int n) { 
      if (n == 1) 
       return false; 
      else { 
       for (int i = 2; i <= n/2; i++) { 
        if (n % i == 0) { 

         return false; 
        } 
       } 

       return true; 
      } 
     } 
    }

來源

2015-06-15 Ujjwal

如果沒有根本改寫，這是不可修復的。例如改變算法。你正在使用最慢的方法之一... –

你可能想研究[Eratosthenes的篩選]（https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）。 –

減少執行時間的一種簡單而快速的方法是改變你的'for'循環，每次增加'i' 2（跳過檢查偶數）。請注意，這需要從3開始，而不是從2開始，最初是'count = 1;'。 – River

做出最簡單的變化是在結束對checkprime循環for已i達到n平方根之後。原因是，如果您發現一個因子大於n的平方根，那意味着有一個因子小於本應該找到的平方根n。

for (int i = 2; i <= Math.sqrt(n); i++) {

此外，如果需要更快的速度，在打印所有素數達到了一個極限的最佳算法是Sieve of Eratosthenes。這涉及替換你擁有的東西。你需要一個數組來標記哪些數字是複合的。從2開始，您會將所有2的倍數標記爲複合。在數組中移動，如果您發現一個未標記爲複合的數字，它就是素數，您可以打印它。對於每個遇到的素數，您都會將該素數的所有倍數標記爲複合素數。

來源

2015-06-15 16:46:42 rgettman

從直覺上來說，我使用'i * i <= n'而不是'i <= Math.sqrt（n）'，它的平方比取平方根更快（可能在今天的CPU上並不重要，儘管）。另外請記住，使用Eratosthenes的Sieve，你將交換內存使用的速度（特別是如果數量很大）。 – mihi

與我跳過偶數相結合的這種優化將導致算法在我看來具有可接受的性能。不，它不是非常快，但它會比沒有優化時快兩倍，因爲您將刪除超過一半的數字，您將檢查失敗。 – jdkorv11

除2以外的任何一個都不會是偶數。素數只能被1和iteslef整除。

此外，你可以檢查它的sqrt。如果到那時你什麼也找不到，那麼這是一個主要的。

 public bool IsPrime(double num) 
    { 
     bool isprime = true; 
     double limit = Math.Sqrt(num); 

     if (num % 2 == 0) 
      return num == 2; 

     if (num == 3 || num == 5 || num == 7) 
      return true; 

     for (int i = 3; i < limit; i++) 
      if (num % 1 == 0) 
       return false; 

     return isprime; 
    }

來源

2015-06-15 16:47:51 GaidenFocus

'我<極限'是錯誤的。 'num％1 == 0'是** always ** true。用'雙'代表質數並不好。 –

您可以找到素數存儲到列表，並做進一步檢查只針對他們（Eratosphenes的篩）：

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

public class PrimeNotillN { 
    public static void main(String[] args) { 
     int n = 1000000; 
     int count = 0; 
     List<Integer> primes = new ArrayList<>(); 

     for (int i = 2; i < n; i++) { 
      boolean res = checkprime(primes, i); 
      if (res) { 
       count++; 
       primes.add(i); 
      } 
     } 
     System.out.println("total prime number till " + n + " is " + count); 
    } 

    private static boolean checkprime(List<Integer> primes, int n) { 
     int fence = (int) Math.sqrt(n); 
     for (int prime : primes) { 
      if (n % prime == 0) { 
       return false; 
      } 
      if (prime >= fence) 
       break; 
     } 

     return true; 
    } 
}

來源

2015-06-15 16:51:46

沒有任何算法可以通過任何數字進行檢查（即試圖分割）Eratosthenes的篩子。整個問題就是*不需要檢查*。複合材料是通過重複添加生成的，剩下的就是*自動*素數。如果測試鴻溝，複雜性顯着惡化。 –

使用的eratoshtenes方法篩和維護所有質數的高速緩存中找到

public int countPrimes(int n) { 
    if(n==0){ 
     return 0; 
    }else{ 
     boolean[] isPrime=new boolean[n]; 
     for(int i=2;i<n;i++){ 
      isPrime[i]=true; 
     } 

     for(int i=2;i*i<n;i++){ 
      if(!isPrime[i]){ 
       continue; 
      } 
      for(int j=i*i;j<n;j+=i){ 
       isPrime[j]=false; 
      } 
     } 

     int counter=0; 
     for(int i=2;i<n;i++){ 
      if(isPrime[i]){ 
       counter++; 
      } 
     } 

     return counter; 

    } 
}

來源

2016-04-02 01:31:12

計算素數直到N

回答

相關問題