java - 素数计算乐趣

Question

我们在这里工作很开心。这一切都始于其中一个人设置了 Hackintosh，我们想知道它是否比我们拥有的（几乎）相同规格的 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 的情节，只是在优化它时获得了一些乐趣。没有优化的第一次尝试（上面的代码有几个）运行了大约 52.6 分钟，以找到前 150000 个素数。此优化运行大约 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

好吧，我看到了一些可以完成的快速优化。首先，您不必尝试每个数字最多为当前数字的一半。

相反，您只需要尝试当前数字的平方根。

另一个优化是 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了。
与将两个数字相乘相比，计算平方根需要很多时间。但是，由于我们将乘法移动到 for 循环中，因此每个循环都执行此操作。因此，这可能会减慢速度，具体取决于 java 中平方根算法的速度。

score 6 · Accepted Answer

这是一个快速简单的解决方案：

找到小于 100000 的素数；在 5 毫秒内找到 9592
找到小于 1000000 的素数；在 20 毫秒内找到了 78498 个
找到小于 10000000 的素数；在 143 毫秒内找到 664579
找到小于 100000000 的素数；5761455 在 2024 毫秒内被发现

找到小于 1000000000 的素数；在 23839 毫秒内发现 50847534

//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 个素数需要我们不到一秒钟（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

请记住，有更好的方法来寻找素数......

我认为你可以采取这个循环：

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

并使其计数器变量 i 从 3 开始，并且只尝试对奇数进行 mod，因为除 2 之外的所有素数都不能被任何偶数整除。

score 1 · Accepted Answer

是否重新声明变量素数

        while (count < topPrime) {

            boolean prime = true;

在循环内使其效率低下？（我认为这无关紧要，因为我认为 Java 会对此进行优化）

boolean prime;        
while (count < topPrime) {

            prime = true;

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;
    }
}

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 中尝试使用带标签的 continue ......
我知道我跳过了前几个素数的计算，但它们是众所周知的，没有必要重新计算它们。:-) 如果需要，我可以对他们的输出进行硬编码！此外，它无论如何都没有决定性的优势。

结果：

-- First
Last prime = 2015201
总时间 = 4.281

-- 倒数第二个
素数 = 2015201
总时间 = 0.953

不错。我想可能会有所改进，但过多的优化会扼杀好的代码。

score 0 · Accepted Answer

您应该能够通过仅评估奇数来使内部循环快两倍。不确定这是否是有效的 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

我决定在 F# 中尝试这个，这是我第一次体面的尝试。在我的 2.2Ghz Core 2 Duo 上使用 Eratosthenes 筛，它在大约 200 毫秒内通过 2..150,000。每次它调用它自己时，它都会从列表中消除当前的倍数，所以它会随着它的进行而变得更快。这是我在 F# 中的第一次尝试，因此我们将不胜感激任何建设性的意见。

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

我敢打赌米勒-拉宾会更快。如果您测试足够多的连续数字，它就会变得确定性，但我什至不会打扰。一旦随机算法达到其失败率等于 CPU 打嗝导致错误结果的可能性的程度，它就不再重要了。

score 0 · Accepted Answer

这是我的解决方案......它相当快......它在我的机器（核心 i7 @ 2.93Ghz）上的 Vista64 上在 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

@Mark Ransom -不确定这是否是 java 代码

他们可能会抱怨，但我希望使用我已经学会信任 Java 的范式重写，他们说要玩得开心，请确保他们理解规范没有说明对返回的结果集进行排序，你也会转换结果集点值（）到我在记事本中一次性完成的列表类型，然后再做一个小差事

=============== 开始未经测试的代码 ===============

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 树，因此可以将结果堆叠起来，直到机器开始出现故障，然后该起点可以用于另一块测试 == 一次运行的结束用作另一次运行的构造函数值，坚持已经完成的磁盘工作并允许增量前馈设计。现在烧坏了，循环逻辑需要分析。

补丁（加上添加 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 毫秒。我将所有计算出的素数保存在一个数组中，并且只尝试除数直到数的 sqrt。当然，当我们需要非常多的素数（尝试使用 100000000）时，这不起作用，因为数组变得太大并给出 seg 错误。

/*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]);
}

$时间./a.out
最后一个素数 = 163841
实际0m0.045s
用户 0m0.040s
系统 0m0.004s

score 0 · Accepted Answer

当我开始阅读这篇关于素数的博客文章时，我在机器的某个地方发现了这段代码。代码在 C# 中，我使用的算法来自我的脑海，尽管它可能在 Wikipedia 上的某个地方。;) 无论如何，它可以在大约 300 毫秒内获取前 150000 个素数。我发现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

这是我的贡献：

机器：2.4GHz 四核 i7 w/8GB RAM @ 1600MHz

编译器：clang++ main.cpp -O3

基准：

Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100

Calculated 25 prime numbers up to 100 in 2 clocks (0.000002 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000

Calculated 168 prime numbers up to 1000 in 4 clocks (0.000004 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000

Calculated 1229 prime numbers up to 10000 in 18 clocks (0.000018 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000

Calculated 9592 prime numbers up to 100000 in 237 clocks (0.000237 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000

Calculated 78498 prime numbers up to 1000000 in 3232 clocks (0.003232 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000000

Calculated 664579 prime numbers up to 10000000 in 51620 clocks (0.051620 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000000

Calculated 5761455 prime numbers up to 100000000 in 918373 clocks (0.918373 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000000

Calculated 50847534 prime numbers up to 1000000000 in 10978897 clocks (10.978897 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 4000000000

Calculated 189961812 prime numbers up to 4000000000 in 53709395 clocks (53.709396 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$

来源：

#include <iostream> // cout
#include <cmath> // sqrt
#include <ctime> // clock/CLOCKS_PER_SEC
#include <cstdlib> // malloc/free

using namespace std;

int main(int argc, const char * argv[]) {
    if(argc == 1) {
        cout << "Please enter a number." << "\n";
        return 1;
    }
    long n = atol(argv[1]);
    long i;
    long j;
    long k;
    long c;
    long sr;
    bool * a = (bool*)malloc((size_t)n * sizeof(bool));

    for(i = 2; i < n; i++) {
        a[i] = true;
    }

    clock_t t = clock();

    sr = sqrt(n);
    for(i = 2; i <= sr; i++) {
        if(a[i]) {
            for(k = 0, j = 0; j <= n; j = (i * i) + (k * i), k++) {
                a[j] = false;
            }
        }
    }

    t = clock() - t;

    c = 0;
    for(i = 2; i < n; i++) {
        if(a[i]) {
            //cout << i << " ";
            c++;
        }
    }

    cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";

    free(a);

    return 0;
}

这使用了 Erastothenes 筛法，我已经根据我的知识尽可能地优化了它。欢迎改进。

java - 素数计算乐趣

18 回答 18

Related

Reference