java 质数计算的乐趣
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/288200/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Prime number calculation fun
提问by Feet
We're having a bit of fun here at work. It all started with one of the guys setting up a Hackintosh and we were wondering whether it was faster than a Windows Box of (nearly) same specs that we have. So we decided to write a little test for it. Just a simple Prime number calculator. It's written in Java and tells us the time it takes to calculate the first n Prime numbers.
我们在工作中玩得很开心。这一切都始于一个人设置了 Hackintosh，我们想知道它是否比我们拥有的（几乎）相同规格的 Windows Box 更快。所以我们决定为它写一个小测试。只是一个简单的素数计算器。它是用 Java 编写的，并告诉我们计算前 n 个素数所需的时间。
Optimised version below - now takes ~6.6secs
下面的优化版本 - 现在需要约 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);
}
}
We've pretty much lost the plot of the whole Hackintosh vs PC thing and are just having some fun with optimising it. First attempt with no optimisations (the above code has a couple) ran around 52.6min to find the first 150000 prime numbers. This optimisation is running around 47.2mins.
我们几乎失去了整个 Hackintosh vs PC 的情节，只是在优化它时获得了一些乐趣。第一次没有优化的尝试（上面的代码有几个）运行了大约 52.6 分钟以找到前 150000 个素数。此优化运行大约 47.2 分钟。
If you want to have a go and post your results, then stick em up.
如果你想试一试并发布你的结果，然后把它们贴出来。
Specs for the PC I'm running it on are Pentium D 2.8GHz, 2GB RAM, running Ubuntu 8.04.
我运行它的 PC 的规格是 Pentium D 2.8GHz，2GB RAM，运行 Ubuntu 8.04。
Best Optimisation so far has been the square root of current, first mentioned by Jason Z.
迄今为止最好的优化一直是电流的平方根，首先由 Jason Z 提到。
采纳答案by Sani Singh Huttunen
Well I see a couple of quick optimizations that can be done. First you don't have to try each number up to half of the current number.
好吧，我看到了一些可以完成的快速优化。首先，您不必尝试每个数字最多为当前数字的一半。
Instead you only have try up to the square root of the current number.
相反，您只需要尝试到当前数字的平方根。
And the other optimization was what BP said with a twist: Instead of
另一个优化是 BP 所说的扭曲：而不是
int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
current++;
else
current += 2;
use
利用
int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;
This should speed things up quite a lot.
这应该会大大加快速度。
Edit:
More optimization courtesy of Joe Pineda:
Remove the variable "top".
编辑：
Joe Pineda 提供的更多优化：
删除变量“top”。
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
If this optimization indeed increases speed is up to java.
Calculating the square root takes a lot of time compared to multiplying two numbers. However since we move the multiplication into the for loop this is done every single loop. So this COULD slow things down depending on how fast the square root algorithm in java is.
如果此优化确实提高了速度，则取决于 java。
与两个数字相乘相比，计算平方根需要很多时间。然而，由于我们将乘法移动到 for 循环中，因此每个循环都会完成。因此，这可能会减慢速度，具体取决于 Java 中的平方根算法的速度。
回答by Stephan Eggermont
That's a bit worse than my sieve did on a 8 Mhz 8088 in turbo pascal in 1986 or so. But that was after optimisations :)
这比我的筛子在 1986 年左右的 8 Mhz 8088 涡轮帕斯卡上做的要差一些。但那是在优化之后:)
回答by Robert J. Walker
Since you're searching for them in ascending order, you could keep a list of the primes you've already found and only check for divisibility against them, since all non-prime numbers can be reduced to a list of lesser prime factors. Combine that with the previous tip about not checking for factors over the square root of the current number, and you'll have yourself a pretty darn efficient implementation.
由于您正在按升序搜索它们，因此您可以保留已找到的素数列表，并仅检查它们的可整性，因为所有非素数都可以简化为较小素数的列表。将其与之前关于不检查当前数字平方根上的因子的技巧相结合，您将拥有一个非常高效的实现。
回答by voidlogic
Here is a fast and simple solution:
这是一个快速而简单的解决方案：
- Finding primes less than 100000; 9592 were found in 5 ms
- Finding primes less than 1000000; 78498 were found in 20 ms
- Finding primes less than 10000000; 664579 were found in 143 ms
- Finding primes less than 100000000; 5761455 were found in 2024 ms
Finding primes less than 1000000000; 50847534 were found in 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(); }
- 寻找小于100000的素数；在 5 毫秒内发现了 9592 个
- 寻找小于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(); }
回答by jfs
It takes us under a second (2.4GHz) to generate the first 150000 prime numbers in Python using Sieve of Eratosthenes:
使用埃拉托色尼筛法在 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]))
Example:
例子：
$ 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]
回答by Aistina
In C#:
在 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;
}
}
Output:
输出：
Total time taken: 2.087 seconds
总耗时：2.087 秒
回答by avgbody
Does the re-declaration of the variable prime
是否重新声明变量素数
while (count < topPrime) {
boolean prime = true;
within the loop make it inefficient? (I assume it doesn't matter, since I would think Java would optimize this)
在循环内使其效率低下？（我认为这无关紧要，因为我认为 Java 会对此进行优化）
boolean prime;
while (count < topPrime) {
prime = true;
回答by BP.
Keeping in mind that there are better ways to look for primes...
请记住，有更好的方法来寻找素数......
I think that you can take this loop:
我认为你可以采取这个循环：
for (int i = 2; i < top; i++)
for (int i = 2; i < top; i++)
and make it so that your counter variable i goes from 3 and only tries to do the mod on odd numbers, since all primes other than 2 are never divisible by any even numbers.
并使您的计数器变量 i 从 3 开始，并且只尝试对奇数进行 mod 运算，因为除 2 以外的所有素数都不能被任何偶数整除。
回答by thephpdev
Here's my contribution:
这是我的贡献：
Machine: 2.4GHz Quad-Core i7 w/ 8GB RAM @ 1600MHz
机器：2.4GHz 四核 i7 w/ 8GB RAM @ 1600MHz
Compiler: clang++ main.cpp -O3
编译器： clang++ main.cpp -O3
Benchmarks:
基准：
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$
Source:
来源：
#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;
}
This uses the Sieve of Erastothenes approach, I've optimised it as much as I can with my knowledge. Improvements welcome.
这使用了 Erastothenes 筛法，我已经尽我所能对其进行了优化。欢迎改进。
回答by Giovanni Galbo
Here's my solution... its fairly fast... it calculates the primes between 1 and 10,000,000 in 3 seconds on my machine (core i7 @ 2.93Ghz) on Vista64.
这是我的解决方案......它相当快......它在 Vista64 上的我的机器（核心 i7 @ 2.93Ghz）上在 3 秒内计算出 1 到 10,000,000 之间的素数。
My solution is in C, but I am not a professional C programmer. Feel free to criticize the algorithm and the code itself :)
我的解决方案是用 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;
}
