Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers

Soonwook Hwang, Kyusik Chung, Dongseung Kim

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    4 Citations (Scopus)

    Abstract

    Algorithms of finding prime numbers up to some integer N by Sieve of Eratosthenes are simple and fast. However, even with the time complexity no greater than O(N In In N), it may take weeks or even years of CPU time if N is large like over 15 decimal digits. No known shortcut was reported yet. We develop efficient parallel algorithms to balance the workload of each computer, and to extend memory limit with disk storage to accommodate Giga-bytes of data. Our experiments show that a complete set of up to 14-digit prime numbers can be found in a week of computing time (CPU time) using our 8 1.6GHz Pentium-4 PCs with Linux and MPI library. Also, by sieve of Eratosthenes, we think it is very unlikely that we can compute all primes up to 20 digits even using the fastest computers in the world.

    Original languageEnglish
    Title of host publicationCIT 2007
    Subtitle of host publication7th IEEE International Conference on Computer and Information Technology
    Pages295-299
    Number of pages5
    DOIs
    Publication statusPublished - 2007
    EventCIT 2007: 7th IEEE International Conference on Computer and Information Technology - Aizu-Wakamatsu, Fukushima, Japan
    Duration: 2007 Oct 162007 Oct 19

    Publication series

    NameCIT 2007: 7th IEEE International Conference on Computer and Information Technology

    Other

    OtherCIT 2007: 7th IEEE International Conference on Computer and Information Technology
    Country/TerritoryJapan
    CityAizu-Wakamatsu, Fukushima
    Period07/10/1607/10/19

    Keywords

    • Cluster computer
    • Load balancing
    • MPI
    • Prime number
    • Sieve of Eratosthenes

    ASJC Scopus subject areas

    • Computer Science Applications
    • Information Systems
    • Software
    • General Mathematics

    Fingerprint

    Dive into the research topics of 'Load balanced parallel prime number generator with sieve of eratosthenes on cluster computers'. Together they form a unique fingerprint.

    Cite this