埃拉托色尼并行算法的筛寻找素数 [英] Parallelizing Sieve of Eratosthenes Algorithm for finding Prime Number

问题描述

埃拉托色尼的方法有两种方式并行化筛

Parallelize Sieve of Eratosthenes method in two ways

1. 在使用Java和
2. 在使用C / C ++与Pthreads中

查找阈值的最佳值2和4核CPU。

Find the best values for THRESHOLD for 2 and 4 Core CPUs.

任何一个可以帮助我如何做到这一点。我学习java和放线; C / C ++，将我需要并行算法有什么事情

can any one help me how to do it. i am learning threads of java & C/C++.what things will i need to parallelize this algorithm

推荐答案

注意使用筛方法来查找素数表，一旦你找到一个素数我 - 设置 I * N 作为非黄金为每个 N 。

Note that using the Sieve of Eratostheens method to find the prime numbers table, once you find a prime number i - you set i*n as non-prime for each n.

请注意，对于2个元素，你知道他们是素数 - I，J 您可以同时做到这一点，我不需要从Ĵ的任何信息，反之亦然。
当然这同样适用于每K个素数。

Note that for 2 elements that you know they are prime numbers - i,j you can do it in parallel, i does not require any information from j and vise versa.
The same of course holds for each k prime numbers.

请注意但是要找到一个数是素 - 取决于最后的计算结果！因此，屏障需要标记号作为非质数，寻找下一任的数的工作。

Note however that finding if a number is prime - depends on last calculations! Thus, a barrier is needed between marking numbers as non-primes and finding next prime number to work with.

一个很好的起点可以是：

A good place to start could be:

repeat until finished filling the table:
    1. Find k prime numbers [serially]
    2. Fill the table for these k numbers [parallely]
    3. after all threads finished step 2 [barrier] - return to 1

因为它似乎功课，我只给这些提示，让你做的工作休息。如果以后有什么具体的问题 - 提出新问题，并告诉我们你已经做了什么

Since it seems homework, I'll only give these hints, and let you do the rest of the work. If you later have any specific problem - ask a new question and show us what you already did.

修改：多了一个重要的提示，注意，如果我为素数，都从获得非素数的计算我将不会影响一个事实，即Ĵ是首要的每个 I＆LT; J＆LT; 2I 。利用这一点来找到 K 素数，你不想比如采取对算法的第一次迭代2,3,4为素数。

EDIT: one more important hint, note that if i is prime, the calculation of all the non prime numbers that derive from i will not affect the fact that j is prime for each i < j < 2i. Use this fact to find the k prime numbers, you don't want for example to take 2,3,4 as prime numbers on your first iteration of the algorithm.

这篇关于埃拉托色尼并行算法的筛寻找素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！