English | 中文

Catalogue

Eratosthenes
└───Eratosthenes        Main project code
│   └───Base            Serial program
│   └───MPI_prime       MPI optimized original version
│   └───noEvent         Uneven optimization
│   └───brastBetter     To optimize broadcasting
│   └───CacheOptimize   cache optimization 
│   └───result          Result file
│       └───result_Initial.txt       MPI optimized original version results 
│       └───result_EvenOP.txt        Uneven optimization results
│       └───result_Bcast.txt         Broadcast optimization results
│       └───result_Cache_Final.txt   Cache optimization results
│       └───Result.xlsx              Summary of Results Analysis
│   
│   └───Parallel design***.pdf       Internship Report
│   └───report.pptx                  Report PPT

Algorithm Introduction

Eratosthenes was an ancient Greek mathematician who was searching for prime numbers within the integer N, A unique method was adopted: first write the numbers of 2 to N on paper:

Draw a circle above 2 and then cross out the other multiples of 2; The first number that is neither circled nor crossed out is 3. Circle it and then cross out the other multiples of 3; The first number that has not been circled or crossed out now is 5. Circle it and cross out the other multiples of 5... and so on, until all numbers less than or equal to N are circled or crossed out. At this point, the circled and uncut numbers are exactly prime numbers less than N.

• As shown in the following figure

• The pseudocode is as follows

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.


for i = 2, 3, 4, ..., not exceeding √n:
	if A[i] is true:
		for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
			A[j] := false
			
Output: all i such that A[i] is true.

Environment

• MSMPI - Microsoft MPI (MS-MPI) is a Microsoft implementation of the Message Passing Interface standard for developing and running parallel applications on the Windows platform.
• Visual Studio 2019 - Development tool
• Other configurations - See PDF report

Features

• Comparative experiment
• Detailed annotations
• Acceleration ratio