Java中的多线程质数查找器
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21666998/
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
Multi-Threaded Prime number Finder in Java
提问by user2216672
I am making a java program that I have to find all prime numbers and the count of the prime numbers up to 200 million. I have to use trial division with static global variable that all the threads share to hold the next number to be checked if prime. As it finds a prime it adds it to a array then displays the array upon completion. here is what I have so far and all my threads are showing the same number of primes found as the total number of primes can anyone help with this.
我正在制作一个java程序，我必须找到所有素数和最多2亿的素数计数。我必须使用带有所有线程共享的静态全局变量的试验除法来保存下一个要检查的数字是否为素数。当它找到一个素数时，它会将它添加到一个数组中，然后在完成时显示该数组。这是我到目前为止所拥有的，我所有的线程都显示了与质数总数相同的质数，任何人都可以帮助解决这个问题。
Main-
主要的-
//*import java.util.Scanner;
public class MultiThreadedPrimeFinder {
static final int nThreads = 2;
public static void main(String[] args) throws InterruptedException{
int t;
int total = 0;
PrimeThread[] pthreads = new PrimeThread[nThreads];
//*Scanner kb = new Scanner(System.in);
//*System.out.println("Enter a Positive Integer: ");
//*long num = kb.nextLong();
long starttime, endtime, runtime, a = 0;
starttime = System.currentTimeMillis();
for(int i = 0; i <10000000; i ++)
a+=i;
for (t=0; t<nThreads; t++)
{
pthreads[t] = new PrimeThread();
pthreads[t].start();
}
for (t=0; t<nThreads; t++)
{
pthreads[t].join();
System.out.println("Thread "+t
+" Prime count: "+ pthreads[t].count);
}
total = PrimeThread.count;
System.out.println("Total prime count: "+total);
for (int i=0;i<100; i++)
System.out.println(""+i+": "+PrimeThread.primes[i]);
endtime = System.currentTimeMillis();
runtime = endtime - starttime;
System.out.println("The run time is " +runtime +" milliseconds");
}
}
Class -
班级 -
public class PrimeThread extends Thread{
static long nextNumber=3;
static final long max = 1000;
public static int count=0;
public long thread = 100;
public static long[] primes = new long[100000];
public void run() {
long myNumber;
while ((myNumber=getNextNumber())<=max) {
primes[0] = 2;
if (prime(myNumber)) {
primes[count++] = myNumber;
}
}
}
public static synchronized long getNextNumber() {
long n = nextNumber;
nextNumber +=2;
return n;
}
public boolean prime(long n) {
int i;
for (i=3; i * i<=n; i+=2)
if (n%i==0) return false;
return true;
}
}
the output looks like this
输出看起来像这样
Thread 0 Prime count: 167
Thread 1 Prime count: 167
Total prime count: 167
0: 2
1: 5
2: 7
3: 11
4: 13
5: 17
6: 19
7: 23
8: 29
9: 31
10: 37
11: 41
12: 43
13: 47
14: 53
15: 59
16: 61
17: 67
18: 71
19: 73
20: 79
21: 83
22: 89
23: 97
24: 101
25: 103
26: 107
27: 109
28: 113
29: 127
30: 131
31: 137
32: 139
33: 149
34: 151
35: 157
36: 163
37: 167
38: 173
39: 179
40: 181
41: 191
42: 193
43: 197
44: 199
45: 211
46: 223
47: 227
48: 229
49: 233
50: 239
51: 241
52: 251
53: 257
54: 263
55: 269
56: 271
57: 277
58: 281
59: 283
60: 293
61: 307
62: 311
63: 313
64: 317
65: 331
66: 337
67: 347
68: 349
69: 353
70: 359
71: 367
72: 373
73: 379
74: 383
75: 389
76: 397
77: 401
78: 409
79: 419
80: 421
81: 431
82: 433
83: 439
84: 443
85: 449
86: 457
87: 461
88: 463
89: 467
90: 479
91: 487
92: 491
93: 499
94: 503
95: 509
96: 521
97: 523
98: 541
99: 547
The run time is 17 milliseconds
采纳答案by Vitruvius
You have
你有
public static int count=0;
which keeps track of the number of primes gotten in total. Since it's static, pthreads[0].count == pthreads[1].count == PrimeThread.count. To see the primes retrieved by the individual threads, add an instance counter:
它跟踪获得的质数总数。既然是static, pthreads[0].count == pthreads[1].count == PrimeThread.count. 要查看各个线程检索到的素数，请添加一个实例计数器：
public int myCount = 0;
....
primes[count++] = myNumber;
myCount++;
...
System.out.println("Thread "+t
+" Prime count: "+ pthreads[t].myCount);
Also, to prevent interleaving of count++, you should synchronize when incrementing it.
此外，为了防止 count++ 交错，您应该在增加它时进行同步。
回答by I?ya Bursov
Despite @Saposhiente answer is correct, I'd like to post proper version for OP to consider and find out other small problems
尽管@Saposhiente 答案是正确的，但我想发布适当的版本供 OP 考虑并找出其他小问题
thread class:
线程类：
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
public class PrimeThread extends Thread {
final public static long[] primes = new long[100000];
static {
primes[0] = 2; // init 1st prime only 1 time
};
final static AtomicLong nextNumber = new AtomicLong(3L);
final static long MAX = 1000L;
public int count = 0; // non static local count
public static AtomicInteger totalCount = new AtomicInteger(); // static global count
public void run() {
long myNumber;
while ((myNumber = nextNumber.getAndAdd(2L)) <= MAX)
if (prime(myNumber)) {
primes[totalCount.incrementAndGet()] = myNumber; // note increment and get instead of get and increment
count++;
}
}
public static boolean prime(final long n) {
final long maxI = (long) Math.sqrt(n); // faster than calculation of i*i each time
for (long i = 3; i <= maxI; i += 2)
if (n%i==0) return false;
return true;
}
}
main program:
主程序：
public class MultiThreadedPrimeFinder {
static final int nThreads = 2;
public static void main(final String[] args) {
final PrimeThread[] pthreads = new PrimeThread[nThreads];
final long starttime = System.nanoTime();
for (int i = 0; i < nThreads; i++) {
pthreads[i] = new PrimeThread();
pthreads[i].start();
}
try {
for (int i = 0; i < nThreads; i++)
pthreads[i].join();
} catch (InterruptedException e) {
}
final long endtime = System.nanoTime(); // measure only actual execution, without any system calls
System.out.println("The run time is " + ((endtime - starttime) / 1000000L) + " milliseconds");
for (int i = 0; i < nThreads; i++)
System.out.println("Thread " + i + " Prime count: " + pthreads[i].count); // output each thread's count
System.out.println("Total prime count: " + PrimeThread.totalCount.get()); // output total count
for (int i = 0; i < 100; i++)
System.out.println(""+i+": "+PrimeThread.primes[i]);
}
}
回答by chad
Can't help you with the multi-threaded aspect, I found this page trying to solve something similar, but your prime finding algorithm has a couple of issues:
无法在多线程方面为您提供帮助，我发现此页面试图解决类似的问题，但是您的主要查找算法有几个问题：
First off, in your run()method, why have the primes[0] = 2inside the while loop? It's getting set each time when it only needs to get set once.
首先，在您的run()方法中，为什么要primes[0] = 2在 while 循环内部？当它只需要设置一次时，它每次都会被设置。
Second, you are skipping 3, which is a prime. This is happening because you set myNumberto 3, but then call getNextNumber()before you check it. Initialize myNumberto 1.
其次，您正在跳过 3，这是一个质数。发生这种情况是因为您设置myNumber为 3，但getNextNumber()在检查之前先调用。初始化myNumber为 1。
