素数计算的乐趣

https://stackoverflow.com/questions/288200

java
primes

08-07-2019
|

题

我们在这里工作很开心。这一切都始于其中一个人安装了一台 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 首先提到。

解决方案

嗯，我看到了几个可以做到的快速优化。首先，您不必尝试每个数字，最多可达当前数字的一半。

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

另一个优化是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提供：
删除变量<！> quot; top <！> quot;。

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

如果这种优化确实增加速度取决于java。
与乘以两个数字相比，计算平方根需要花费大量时间。但是，由于我们将乘法移动到for循环中，因此每个循环都会执行此操作。因此，这可能会降低速度，具体取决于java中的平方根算法的速度。

其他提示

这比我在1986年左右用8 Mhz 8088涡轮帕斯卡的筛子差一点。但那是在优化之后：）

由于你是按升序搜索它们，你可以保留一个你已经找到的素数列表，只检查它们的可分性，因为所有非素数都可以简化为较小的素数列表因素。将其与前一个提示相结合，不检查当前数字的平方根上的因子，您将拥有一个非常有效的实现。

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

查找小于100000的素数；5 毫秒内找到 9592 个

查找小于1000000的素数；20 毫秒内找到 78498 个

查找小于10000000的素数；143 毫秒内找到 664579 个

查找小于100000000的素数；2024 毫秒内发现 5761455 个

查找小于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(); }

我们需要一秒钟（2.4GHz）才能使用Sieve of Eratosthenes在Python中生成第一个150000素数：

#!/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]

在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秒

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

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

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

然后使你的计数器变量i从3开始并且只尝试对奇数进行修改，因为除了2之外的所有素数都不会被任何偶数整除。

是否重新声明变量prime

while (count < topPrime) { boolean prime = true;
循环中的
使其效率低下？（我认为这没关系，因为我认为Java会对此进行优化）

boolean prime; while (count < topPrime) { prime = true;

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

我对优化的看法，避免过于神秘的伎俩。我使用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

- 第二个
最后的素数= 2015201
总时间= 0.953

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

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

我决定在F＃尝试这个，这是我第一次尝试它。在我的2.2Ghz Core 2 Duo上使用Eratosthenes的Sieve，它在大约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

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

这是我的解决方案......它的速度相当快......它可以在我的机器（Core 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; }

这是我的看法。该程序是用C编写的，在我的笔记本电脑上需要50毫秒（Core 2 Duo，1 GB Ram）。我将所有计算出的素数保存在一个数组中，并尝试将其除以直到数字的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]); }

$ time ./a.out Last prime = 163841 real 0m0.045s user 0m0.040s sys 0m0.004s

@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

当我开始阅读关于素数的博客文章时，我在我的机器上找到了这个代码。代码在C＃中，我使用的算法来自我的头脑，虽然它可能在维基百科上的某个地方。 ;）无论如何，它可以在大约300ms内获取前150000个素数。我发现n个第一个奇数的总和等于n ^ 2。同样，在维基百科上可能存在这样的证据。所以知道这一点，我可以写一个算法，它永远不必计算平方根，但我必须逐步计算才能找到素数。所以如果你想要Nth prime，这个算法必须先找到（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; }

这是我的贡献：

机器：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的Sieve方法，我已经根据我的知识尽可能地优化了它。欢迎改进。

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow