java - 素数計算の楽しみ

Question

私たちはここで仕事を楽しんでいます。それはすべて、Hackintosh をセットアップした人の 1 人から始まりました。私たちが持っている (ほぼ) 同じ仕様の Windows Box よりも高速かどうか疑問に思っていました。そこで、ちょっとしたテストを書くことにしました。シンプルな素数計算機です。これは Java で書かれており、最初の n 個の素数を計算するのにかかる時間を教えてくれます。

以下の最適化されたバージョン - 約 6.6 秒かかります

public class Primes {

    public static void main(String[] args) {
        int topPrime = 150000;
        int current = 2;
        int count = 0;
        int lastPrime = 2;

        long start = System.currentTimeMillis();

        while (count < topPrime) {

            boolean prime = true;

            int top = (int)Math.sqrt(current) + 1;

            for (int i = 2; i < top; i++) {
                if (current % i == 0) {
                    prime = false;
                    break;
                }
            }

            if (prime) {
                count++;
                lastPrime = current;
            }
            if (current == 2) {
             current++;
            } else {
                current = current + 2;
            }
        }

        System.out.println("Last prime = " + lastPrime);
        System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
    } 
}

Hackintosh と PC の全体的な筋書きをほとんど失ってしまったので、最適化を楽しんでいます。最適化なしの最初の試行 (上記のコードにはいくつかあります) は、最初の 150000 個の素数を見つけるのに約 52.6 分かかりました。この最適化は約 47.2 分実行されます。

試して結果を投稿したい場合は、貼り付けてください。

私が実行している PC の仕様は、Pentium D 2.8GHz、2GB RAM、Ubuntu 8.04 です。

これまでの最適化の最適化は、Jason Z によって最初に言及された電流の平方根でした。

score 10 · Accepted Answer

これは、私のふるいが 1986 年かそこらでターボパスカルの 8 Mhz 8088 で行ったよりも少し悪いです。しかし、それは最適化の後でした:)

score 9 · Accepted Answer

昇順でそれらを検索しているので、すでに見つけた素数のリストを保持し、素数以外のすべての数をより少ない素因数のリストに減らすことができるため、それらに対して割り切れるかどうかのみをチェックできます。これを、現在の数値の平方根を超える係数をチェックしないという以前のヒントと組み合わせると、非常に効率的な実装ができます。

score 7 · Accepted Answer

実行できる簡単な最適化がいくつか見られます。まず、現在の数値の半分まで各数値を試す必要はありません。

代わりに、現在の数値の平方根まで試すだけです。

そして、もう 1 つの最適化は、BP がひねりを加えて言ったことです。

int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
  current++;
else
  current += 2;

使用する

int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;

これにより、かなり高速化されるはずです。

編集:
Joe Pineda の厚意によるさらなる最適化:
変数 "top" を削除します。

int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;

この最適化によって実際に速度が向上するかどうかは、Java 次第です。
平方根の計算は、2 つの数値の乗算に比べて時間がかかります。ただし、乗算を for ループに移動したため、これはループごとに実行されます。したがって、Java の平方根アルゴリズムの速度によっては、処理が遅くなる可能性があります。

score 6 · Accepted Answer

迅速で簡単な解決策は次のとおりです。

100000 未満の素数を見つける; 9592 件が 5 ミリ秒で見つかりました
1000000 未満の素数を見つける; 20 ミリ秒で 78498 件が見つかりました
10000000 未満の素数を見つける; 143 ミリ秒で 664579 件が見つかりました
100000000 未満の素数を見つける; 2024 ミリ秒で 5761455 件が見つかりました

1000000000 未満の素数を見つける; 50847534 が 23839 ミリ秒で見つかりました

//returns number of primes less than n
private static int getNumberOfPrimes(final int n)
{
    if(n < 2) 
        return 0;
    BitSet candidates = new BitSet(n - 1);
    candidates.set(0, false);
    candidates.set(1, false);
    candidates.set(2, n);
    for(int i = 2; i < n; i++)
        if(candidates.get(i))
            for(int j = i + i; j < n; j += i)
                if(candidates.get(j) && j % i == 0)
                    candidates.set(j, false);            
    return candidates.cardinality();
}

score 4 · Accepted Answer

エラトステネスのふるいを使用して Python で最初の 150000 個の素数を生成するには、1 秒 (2.4GHz) 未満かかります。

#!/usr/bin/env python
def iprimes_upto(limit):
    """Generate all prime numbers less then limit.

    http://stackoverflow.com/questions/188425/project-euler-problem#193605
    """
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

def sup_prime(n):
    """Return an integer upper bound for p(n).

       p(n) < n (log n + log log n - 1 + 1.8 log log n / log n)

       where p(n) is the n-th prime. 
       http://primes.utm.edu/howmany.shtml#2
    """
    from math import ceil, log
    assert n >= 13
    pn = n * (log(n) + log(log(n)) - 1 + 1.8 * log(log(n)) / log(n))
    return int(ceil(pn))

if __name__ == '__main__':
    import sys
    max_number_of_primes = int(sys.argv[1]) if len(sys.argv) == 2 else 150000
    primes = list(iprimes_upto(sup_prime(max_number_of_primes)))
    print("Generated %d primes" % len(primes))
    n = 100
    print("The first %d primes are %s" % (n, primes[:n]))

例：

$ python primes.py

Generated 153465 primes
The first 100 primes are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

score 2 · Accepted Answer

C# の場合:

class Program
{
    static void Main(string[] args)
    {
        int count = 0;
        int max = 150000;
        int i = 2;

        DateTime start = DateTime.Now;
        while (count < max)
        {
            if (IsPrime(i))
            {
                count++;
            }

            i++;

        }
        DateTime end = DateTime.Now;

        Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
        Console.ReadLine();
    }

    static bool IsPrime(int n)
    {
        if (n < 4)
            return true;
        if (n % 2 == 0)
            return false;

        int s = (int)Math.Sqrt(n);
        for (int i = 2; i <= s; i++)
            if (n % i == 0)
                return false;

        return true;
    }
}

出力：

合計所要時間: 2.087 秒

score 1 · Accepted Answer

変数素数の再宣言を行います

        while (count < topPrime) {

            boolean prime = true;

ループ内で非効率になりますか？（Javaがこれを最適化すると思うので、問題ではないと思います）

boolean prime;        
while (count < topPrime) {

            prime = true;

score 1 · Accepted Answer

素数を探すためのより良い方法があることに留意してください...

このループを取ることができると思います：

for (int i = 2; i < top; i++)

2 以外のすべての素数は偶数で割り切れないため、カウンター変数 i が 3 から始まり、奇数でのみ mod を試行するようにします。

score 0 · Accepted Answer

あまりにも不可解なトリックを避けて、最適化を考えています。私はI-GIVE-TERRIBLE-ADVICEによって与えられたトリックを使用しますが、それは私が知っていて忘れていました... :-)

public class Primes
{
  // Original code
  public static void first()
  {
    int topPrime = 150003;
    int current = 2;
    int count = 0;
    int lastPrime = 2;

    long start = System.currentTimeMillis();

    while (count < topPrime) {

      boolean prime = true;

      int top = (int)Math.sqrt(current) + 1;

      for (int i = 2; i < top; i++) {
        if (current % i == 0) {
          prime = false;
          break;
        }
      }

      if (prime) {
        count++;
        lastPrime = current;
//      System.out.print(lastPrime + " "); // Checking algo is correct...
      }
      if (current == 2) {
        current++;
      } else {
        current = current + 2;
      }
    }

    System.out.println("\n-- First");
    System.out.println("Last prime = " + lastPrime);
    System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
  }

  // My attempt
  public static void second()
  {
    final int wantedPrimeNb = 150000;
    int count = 0;

    int currentNumber = 1;
    int increment = 4;
    int lastPrime = 0;

    long start = System.currentTimeMillis();

NEXT_TESTING_NUMBER:
    while (count < wantedPrimeNb)
    {
      currentNumber += increment;
      increment = 6 - increment;
      if (currentNumber % 2 == 0) // Even number
        continue;
      if (currentNumber % 3 == 0) // Multiple of three
        continue;

      int top = (int) Math.sqrt(currentNumber) + 1;
      int testingNumber = 5;
      int testIncrement = 2;
      do
      {
        if (currentNumber % testingNumber == 0)
        {
          continue NEXT_TESTING_NUMBER;
        }
        testingNumber += testIncrement;
        testIncrement = 6 - testIncrement;
      } while (testingNumber < top);
      // If we got there, we have a prime
      count++;
      lastPrime = currentNumber;
//      System.out.print(lastPrime + " "); // Checking algo is correct...
    }

    System.out.println("\n-- Second");
    System.out.println("Last prime = " + lastPrime);
    System.out.println("Total time = " + (double) (System.currentTimeMillis() - start) / 1000);
  }

  public static void main(String[] args)
  {
    first();
    second();
  }
}

はい、Javaで初めて試すときは、ラベル付きの続行を使用しました...
最初のいくつかの素数の計算をスキップすることは知っていますが、それらはよく知られており、再計算する意味がありません。:-)必要に応じて、出力をハードコーディングできます。その上、それはとにかく決定的なエッジを与えません。

結果：

-最初
の最後の素数=2015201
合計時間=4.281

-
最後から2番目の素数=2015201
合計時間=0.953

悪くない。少し改善されるかもしれませんが、最適化が多すぎると良いコードが失われる可能性があります。

score 0 · Accepted Answer

奇数を評価するだけで、内部ループを2倍速くすることができるはずです。これが有効なJavaであるかどうかはわかりませんが、私はC ++に慣れていますが、適応できると確信しています。

            if (current != 2 && current % 2 == 0)
                    prime = false;
            else {
                    for (int i = 3; i < top; i+=2) {
                            if (current % i == 0) {
                                    prime = false;
                                    break;
                            }
                    }
            }

score 0 · Accepted Answer

@ Mark Ransom -これが Java コードかどうかわからない

彼らはおそらくうめき声を上げるでしょうが、私は Java で信頼することを学んだパラダイムを使用して書き直したいと思っていました。短い用事をする前に、メモ帳で 1 回限りのことを指定して、ドット値 () をリスト型に変換します。

=============== テストされていないコードの開始 ===============

package demo;

import java.util.List;
import java.util.HashSet;

class Primality
{
  int current = 0;
  int minValue;
  private static final HashSet<Integer> resultSet = new HashSet<Integer>();
  final int increment = 2;
  // An obvious optimization is to use some already known work as an internal
  // constant table of some kind, reducing approaches to boundary conditions.
  int[] alreadyKown = 
  {
     2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
     43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
     127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
     199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
     283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
     383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
     467, 479, 487, 491, 499, 503, 509, 521, 523, 541
  };
  // Trivial constructor.

  public Primality(int minValue)
   {
      this.minValue = minValue;
  }
  List calcPrimes( int startValue )
  {
      // eliminate several hundred already known primes 
      // by hardcoding the first few dozen - implemented 
      // from prior work by J.F. Sebastian
      if( startValue > this.minValue )
      {
          // Duh.
          current = Math.abs( start );
           do
           {
               boolean prime = true;
               int index = current;
               do
               {
                  if(current % index == 0)
                  {
                      // here, current cannot be prime so break.
                      prime = false;
                      break;
                   }
               while( --index > 0x00000000 );

               // Unreachable if not prime
               // Here for clarity

               if ( prime )
               {     
                   resultSet dot add ( or put or whatever it is )
                           new Integer ( current ) ;
               }
           }
           while( ( current - increment ) > this.minValue );
           // Sanity check
           if resultSet dot size is greater that zero
           {
              for ( int anInt : alreadyKown ) { resultSet.add( new Integer ( anInt ) );}
             return resultSet;
           }
           else throw an exception ....
      }

=============== テストされていないコードの終了 ===============

ハッシュセットを使用すると、結果を B ツリーとして検索できるため、マシンが故障し始めるまで結果を積み重ねることができ、その開始点を別のテストブロックに使用できます == 別の実行のコンストラクタ値として使用される 1 つの実行の終わり、すでに完了したディスク作業に永続化され、インクリメンタルなフィードフォワード設計が可能になります。現在燃え尽きており、ループロジックは分析が必要です。

パッチ (さらに sqrt を追加) :

  if(current % 5 == 0 )
  if(current % 7 == 0 )
  if( ( ( ( current % 12 ) +1 ) == 0) || ( ( ( current % 12 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 18 ) +1 ) == 0) || ( ( ( current % 18 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 24 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 36 ) +1 ) == 0) || ( ( ( current % 36 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 42 ) -1 ) == 0) ){break;}


// and - new work this morning:


package demo;

/**
 *
 * Buncha stuff deleted for posting .... duh.
 *
 * @author  Author
 * @version 0.2.1
 *
 * Note strings are base36
 */
public final class Alice extends java.util.HashSet<java.lang.String>
{
    // prints 14551 so it's 14 ½ seconds to get 40,000 likely primes
    // using Java built-in on amd sempron 1.8 ghz / 1600 mhz front side bus 256 k L-2
    public static void main(java.lang.String[] args)
    {
        try
        {
            final long start=System.currentTimeMillis();
            // VM exhibits spurious 16-bit pointer behaviour somewhere after 40,000
            final java.lang.Integer upperBound=new java.lang.Integer(40000);
            int index = upperBound.intValue();

            final java.util.HashSet<java.lang.String>hashSet
            = new java.util.HashSet<java.lang.String>(upperBound.intValue());//
            // Arbitraily chosen value, based on no idea where to start.
            java.math.BigInteger probablePrime
            = new java.math.BigInteger(16,java.security.SecureRandom.getInstance("SHA1PRNG"));
            do
            {
                java.math.BigInteger nextProbablePrime = probablePrime.nextProbablePrime();
                if(hashSet.add(new java.lang.String(nextProbablePrime.toString(Character.MAX_RADIX))))
                {
                    probablePrime = nextProbablePrime;
                    if( ( index % 100 ) == 0x00000000 )
                    {
                        // System.out.println(nextProbablePrime.toString(Character.MAX_RADIX));//
                        continue;
                    }
                    else
                    {
                        continue;
                    }
                }
                else
                {
                    throw new StackOverflowError(new String("hashSet.add(string) failed on iteration: "+
                    Integer.toString(upperBound.intValue() - index)));
                }
            }
            while(--index > 0x00000000);
            System.err.println(Long.toString( System.currentTimeMillis() - start));
        }
        catch(java.security.NoSuchAlgorithmException nsae)
        {
            // Never happen
            return;
        }
        catch(java.lang.StackOverflowError soe)
        {
            // Might happen
            System.out.println(soe.getMessage());//
            return;
        }
    }
}// end class Alice

score 0 · Accepted Answer

これが私の見解です。このプログラムは C で書かれており、私のラップトップ (Core 2 Duo、1 GB RAM) では 50 ミリ秒かかります。計算されたすべての素数を配列に保持し、数の平方根までのみ割り切れるようにしています。もちろん、非常に多数の素数 (100000000 で試行) が必要な場合、配列が大きくなりすぎてセグフォールトが発生するため、これは機能しません。

/*Calculate the primes till TOTALPRIMES*/
#include <stdio.h>
#define TOTALPRIMES 15000

main(){
int primes[TOTALPRIMES];
int count;
int i, j, cpr;
char isPrime;

primes[0] = 2;
count = 1;

for(i = 3; count < TOTALPRIMES; i+= 2){
    isPrime = 1;

    //check divisiblity only with previous primes
    for(j = 0; j < count; j++){
        cpr = primes[j];
        if(i % cpr == 0){
            isPrime = 0;
            break;
        }
        if(cpr*cpr > i){
            break;
        }
    }
    if(isPrime == 1){
        //printf("Prime: %d\n", i);
        primes[count] = i;
        count++;
    }


}

printf("Last prime = %d\n", primes[TOTALPRIMES - 1]);
}

$ time ./a.out
最後の素数 = 163841
実質 0m0.045s
ユーザー 0分0.040秒
システム 0m0.004s

score 0 · Accepted Answer

私はこれを F# で試すことにしました。これは、最初のまともな試みです。私の 2.2Ghz Core 2 Duo でエラトステネスのふるいを使用すると、約 200 ミリ秒で 2..150,000 を実行します。自分自身を呼び出すたびに、現在の倍数がリストから削除されるため、進むにつれて高速になります。これは F# での私の最初の試みの 1 つなので、建設的なコメントをいただければ幸いです。

let max = 150000
let numbers = [2..max]
let rec getPrimes sieve max =
    match sieve with
    | [] -> sieve
    | _ when sqrt(float(max)) < float sieve.[0] -> sieve
    | _ -> let prime = sieve.[0]
           let filtered = List.filter(fun x -> x % prime <> 0) sieve // Removes the prime as well so the recursion works correctly.
           let result = getPrimes filtered max
           prime::result        // The filter removes the prime so add it back to the primes result.

let timer = System.Diagnostics.Stopwatch()
timer.Start()
let r = getPrimes numbers max
timer.Stop()
printfn "Primes: %A" r
printfn "Elapsed: %d.%d" timer.Elapsed.Seconds timer.Elapsed.Milliseconds

score 0 · Accepted Answer

Miller-Rabinの方が速いに違いない。十分な連続数をテストすると、決定論的になりますが、私は気にしません。ランダム化されたアルゴリズムが、その失敗率が CPU ヒカップが間違った結果を引き起こす可能性と等しくなるポイントに達すると、それはもはや問題ではなくなります。

score 0 · Accepted Answer

これが私の解決策です...かなり高速です...Vista64の私のマシン（コアi7 @ 2.93Ghz）で3秒で1から10,000,000の間の素数を計算します。

私のソリューションは C ですが、私はプロの C プログラマーではありません。アルゴリズムとコード自体を自由に批判してください:)

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

//5MB... allocate a lot of memory at once each time we need it
#define ARRAYMULT 5242880 


//list of calculated primes
__int64* primes; 
//number of primes calculated
__int64 primeCount;
//the current size of the array
__int64 arraySize;

//Prints all of the calculated primes
void PrintPrimes()
{
    __int64 i;
    for(i=0; i<primeCount; i++)
    {
        printf("%d ", primes[i]);
    }

}

//Calculates all prime numbers to max
void CalcPrime(__int64 max)
{
    register __int64 i;
    double square;
    primes = (__int64*)malloc(sizeof(__int64) * ARRAYMULT);
    primeCount = 0;
    arraySize = ARRAYMULT;

    //we provide the first prime because its even, and it would be convenient to start
    //at an odd number so we can skip evens.
    primes[0] = 2;
    primeCount++;



    for(i=3; i<max; i+=2)
    {
        int j;
        square = sqrt((double)i);

        //only test the current candidate against other primes.
        for(j=0; j<primeCount; j++)
        {
            //prime divides evenly into candidate, so we have a non-prime
            if(i%primes[j]==0)
                break;
            else
            {
                //if we've reached the point where the next prime is > than the square of the
                //candidate, the candidate is a prime... so we can add it to the list
                if(primes[j] > square)
                {
                    //our array has run out of room, so we need to expand it
                    if(primeCount >= arraySize)
                    {
                        int k;
                        __int64* newArray = (__int64*)malloc(sizeof(__int64) * (ARRAYMULT + arraySize));

                        for(k=0; k<primeCount; k++)
                        {
                            newArray[k] = primes[k];
                        }

                        arraySize += ARRAYMULT;
                        free(primes);
                        primes = newArray;
                    }
                    //add the prime to the list
                    primes[primeCount] = i;
                    primeCount++;
                    break;

                }
            }

        }

    }


}
int main()
{
    int max;
    time_t t1,t2;
    double elapsedTime;

    printf("Enter the max number to calculate primes for:\n");
    scanf_s("%d",&max);
    t1 = time(0);
    CalcPrime(max);
    t2 = time(0);
    elapsedTime = difftime(t2, t1);
    printf("%d Primes found.\n", primeCount);
    printf("%f seconds elapsed.\n\n",elapsedTime);
    //PrintPrimes();
    scanf("%d");
    return 1;
}

score 0 · Accepted Answer

素数に関するこのブログエントリを読み始めたときに、マシンのどこかにこのコードを見つけました。コードは C# で書かれており、私が使用したアルゴリズムは私の頭に浮かんだものですが、おそらくウィキペディアのどこかにあります。;) とにかく、最初の 150000 個の素数を約 300ms で取得できます。最初の n 個の奇数の合計が n^2 になることを発見しました。繰り返しますが、おそらくウィキペディアのどこかにこれの証拠があります。これを知っていれば、平方根を計算する必要はないアルゴリズムを書くことができますが、素数を見つけるために段階的に計算する必要があります。したがって、N 番目の素数が必要な場合、このアルゴリズムは前に (N-1) 個の素数を見つける必要があります。それで、それはあります。楽しみ！


//
// Finds the n first prime numbers.
//
//count: Number of prime numbers to find.
//listPrimes: A reference to a list that will contain all n first prime if getLast is set to false.
//getLast: If true, the list will only contain the nth prime number.
//
static ulong GetPrimes(ulong count, ref IList listPrimes, bool getLast)
{
    if (count == 0)
        return 0;
    if (count == 1)
    {
        if (listPrimes != null)
        {
            if (!getLast || (count == 1))
                listPrimes.Add(2);
        }

        return count;
    }

    ulong currentSquare = 1;
    ulong nextSquare = 9;
    ulong nextSquareIndex = 3;
    ulong primesCount = 1;

    List dividers = new List();

    //Only check for odd numbers starting with 3.
    for (ulong curNumber = 3; (curNumber  (nextSquareIndex % div) == 0) == false)
                dividers.Add(nextSquareIndex);

            //Move to next square number
            currentSquare = nextSquare;

            //Skip the even dividers so take the next odd square number.
            nextSquare += (4 * (nextSquareIndex + 1));
            nextSquareIndex += 2;

            //We may continue as a square number is never a prime number for obvious reasons :).
            continue;
        }

        //Check if there is at least one divider for the current number.
        //If so, this is not a prime number.
        if (dividers.Exists(div => (curNumber % div) == 0) == false)
        {
            if (listPrimes != null)
            {
                //Unless we requested only the last prime, add it to the list of found prime numbers.
                if (!getLast || (primesCount + 1 == count))
                    listPrimes.Add(curNumber);
            }
            primesCount++;
        }
    }

    return primesCount;
}

score 0 · Accepted Answer

C#

Aistina のコードの拡張:

これは、3 より大きいすべての素数が 6n + 1 または 6n - 1 の形式であるという事実を利用しています。

これは、ループを通過するたびに 1 ずつインクリメントするよりも、約 4 ～ 5% 速度が向上しました。

class Program
{       
    static void Main(string[] args)
    {
        DateTime start = DateTime.Now;

        int count = 2; //once 2 and 3

        int i = 5;
        while (count < 150000)
        {
            if (IsPrime(i))
            {
                count++;
            }

            i += 2;

            if (IsPrime(i))
            {
                count++;
            }

            i += 4;
        }

        DateTime end = DateTime.Now;

        Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
        Console.ReadLine();
    }

    static bool IsPrime(int n)
    {
        //if (n < 4)
        //return true;
        //if (n % 2 == 0)
        //return false;

        int s = (int)Math.Sqrt(n);
        for (int i = 2; i <= s; i++)
            if (n % i == 0)
                return false;

        return true;
    }
}

java - 素数計算の楽しみ

18 に答える 18

Related

Reference