素数计算的乐趣
我们在工作中有点乐趣。 这一切都始于其中一个人设置了一个Hackintosh，我们想知道它是否比我们拥有的（几乎）相同规格的Windows Box更快。 所以我们决定为它写一点测试。 只是一个简单的Prime数字计算器。 它是用Java编写的，它告诉我们计算前n个Prime数字所需的时间。
下面的优化版本 – 现在需要~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提供：
删除变量“top”。
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
- 寻找不到1亿的素数; 在2024 ms发现5761455
-
寻找低于10亿的素数; 50847534在23839 ms内被发现
//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的事实。
对于每次通过循环，这增加了大约4-5％的速度增加1。
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(); } }
是的，我使用标记为continue，第一次在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打嗝导致错误结果的可能性的程度，它就不再重要了。
这是我的解决方案……它相当快……它在Vista64上计算机器（核心i7 @ 2.93Ghz）3秒内的1到10,000,000之间的质数。
我的解决方案是C语言，但我不是专业的C程序员。 随意批评算法和代码本身:)
#include #include #include #include //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 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
这是我的看法。 该程序是用C写的，在我的笔记本电脑上需要50毫秒（Core 2 Duo，1 GB Ram）。 我将所有计算出的素数保存在一个数组中，并尝试除法直到数量的sqrt。 当然，当我们需要非常大量的素数（尝试使用100000000）时，这不起作用，因为数组变得太大并且给出了seg错误。
/*Calculate the primes till TOTALPRIMES*/ #include #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 用户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 resultSet = new HashSet (); 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 JF 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 { // 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.HashSethashSet = new java.util.HashSet(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 // cout #include // sqrt #include // clock/CLOCKS_PER_SEC #include // 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方法，我已经根据我的知识尽可能地优化了它。 改进欢迎。