# 關於用 Pthread 取質數的問題
###### tags: `Linux 系統與程式設計`

## 前言
從 1 - 100 之間取出所有的質數，利用 threads 來分配計算質數的範圍。

## 一、輸出有問題
### (一) 原本的程式

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h> 
#include <time.h>

#define NUM_THREADS 10
#define MSIZE 100

// 找出 1 - 100 的所有質數

static double getDoubleTime();
void *thread_function(void *arg);
pthread_mutex_t work_mutex;


int main(void) {
	int res;
	pthread_t a_thread[NUM_THREADS];
	void *thread_result;
	int lots_of_threads;
	
	// start to measure time...
	double start_time = getDoubleTime();
	
	// initialize mutex...
	res = pthread_mutex_init(&work_mutex, NULL);
	if (res != 0) {
       	perror("Mutex initialization failed");
	    exit(EXIT_FAILURE);
    }

	// pthread_create...
	for (lots_of_threads = 0; lots_of_threads < NUM_THREADS; lots_of_threads ++) {
		res = pthread_create(&(a_thread[lots_of_threads]), NULL, thread_function, (void*)(long)lots_of_threads);
	
        if (res != 0) {
			perror("Thread creation failed");
        		exit(EXIT_FAILURE);
		}
	}

	// pthread_join...
	for (lots_of_threads = NUM_THREADS - 1; lots_of_threads >= 0; lots_of_threads--) {
        	res = pthread_join(a_thread[lots_of_threads], &thread_result);
    
            if (res != 0) {
	            perror("pthread_join failed");
        	}
    }	

	printf("\nThread joined\n");

	// stop measuring time...
	double finish_time = getDoubleTime();
	printf("Execute Time:  %.3lf ms\n", (finish_time - start_time));
    exit(EXIT_SUCCESS);
}


void *thread_function(void *arg) {
    // pthread_mutex_lock(&work_mutex);
	
    int my_num = (long)arg;
	// if (MSIZE % NUM_THREADS != 0){    printf("error");   pthread_exit(-1);    }

    int start_num = (MSIZE / NUM_THREADS) * my_num + 1;
	int end_num = (MSIZE / NUM_THREADS) * (my_num + 1);

    int i = 0, j = 0;   // Set the loop
    int count = 0;      // Set the counter
    int result = 0;     // result

	printf("\n\nI'm thread[%d], start_num:%d, end_num:%d\n", my_num, start_num, end_num);

    /* find the prime number */
    for (i = start_num; i <= end_num; i++) {
        count = 0;      // Reset counter

        for (j = 1; j <= i; j++) {
            if (i % j == 0)
                count += 1;
        }
        
        if (count == 2) { 
            result = i;
            printf("%d\t", result);
        }
    }

    // pthread_mutex_unlock(&work_mutex);
	pthread_exit(0);
}


static double getDoubleTime() {
        struct timeval tm_tv;
        gettimeofday(&tm_tv,0);
        return (double)(((double)tm_tv.tv_sec * (double)1000. + (double)(tm_tv.tv_usec)) * (double)0.001);
}

* [執行結果]

### (二) 做個測試，來看看是怎麼一回事
* 目前的假設
> 當ㄧ個 thread 還沒 printf 完它所負責範圍的質數時，就被切換到另一個 thread 裡面執行。
* 參考資料
* [Using mutex for pthread results in random answer](http://stackoverflow.com/questions/15811605/using-mutex-for-pthread-results-in-random-answer)


* 驗證假設
* 為了驗證假設的正確性，我在 printf 質數時後面再補上該質數所對應的 thread number，作法如下：

   /* 前面省略 */
   
   /* find the prime number */
    for (i = start_num; i <= end_num; i++) {
        count = 0;      // Reset counter

        for (j = 1; j <= i; j++) {
            if (i % j == 0)
                count += 1;
        }
        
        if (count == 2) { 
            result = i;
            printf("%d-[%d]\t", result, my_num);
        }
    }
    
    /* 後面省略 */

* [執行結果]

> 看來前面的假設是正確的，但是我們該如何避免這種情形？

## 二、輸出正確
### (一) 利用陣列儲存質數、在 main() 裡面輸出陣列
* 這個方法比較繁瑣，需要事先宣告陣列來儲存質數。在執行 threads 時將對應的質數儲存至陣列，接著再回到 main() 裡面輸出結果。

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h> 
#include <time.h>

#define NUM_THREADS 10
#define MSIZE 100

// 找出 1 - 100 的所有質數

static double getDoubleTime();
void *thread_function(void *arg);
pthread_mutex_t work_mutex;

// 宣告 prime_array 陣列
int prime_array[NUM_THREADS][(MSIZE / NUM_THREADS)];


int main(void) {
	int res;
	pthread_t a_thread[NUM_THREADS];
	void *thread_result;
	int lots_of_threads;
    int print_prime = 0;


	// start to measure time...
	double start_time = getDoubleTime();
	
	// initialize mutex...
	res = pthread_mutex_init(&work_mutex, NULL);
	if (res != 0) {
       	perror("Mutex initialization failed");
	    exit(EXIT_FAILURE);
    }

	// pthread_create...
	for (lots_of_threads = 0; lots_of_threads < NUM_THREADS; lots_of_threads ++) {
		res = pthread_create(&(a_thread[lots_of_threads]), NULL, thread_function, (void*)(long)lots_of_threads);

        if (res != 0) {
			perror("Thread creation failed");
        		exit(EXIT_FAILURE);
		}
	}

	// pthread_join...
	for (lots_of_threads = NUM_THREADS - 1; lots_of_threads >= 0; lots_of_threads--) {
        	res = pthread_join(a_thread[lots_of_threads], &thread_result); 

            if (res != 0) {
	            perror("pthread_join failed");
        	}
    }	
    
    /* 輸出 prime_array 陣列 */
    int i = 0;  // 設定計數器
    for (lots_of_threads = 0; lots_of_threads < NUM_THREADS; lots_of_threads ++) { 
        printf("\n\nThe thread[%d]'s numbers：\n", lots_of_threads);
        
        for (i = 0; i < (MSIZE / NUM_THREADS); i++) {
            if (prime_array[lots_of_threads][i] != 0)
                printf("%d\t", prime_array[lots_of_threads][i]);                        }
    }

	printf("\nThread joined\n");

	// stop measuring time...
	double finish_time = getDoubleTime();
	printf("Execute Time:  %.3lf ms\n", (finish_time - start_time));
    exit(EXIT_SUCCESS);
}


void *thread_function(void *arg) {
    // pthread_mutex_lock(&work_mutex);
	
    int my_num = (long)arg;
	// if (MSIZE % NUM_THREADS != 0){    printf("error");   pthread_exit(-1);    }

    int start_num = (MSIZE / NUM_THREADS) * my_num + 1;
	int end_num = (MSIZE / NUM_THREADS) * (my_num + 1);

    int i = 0, j = 0, k = 0;   // Set the loop
    int count = 0;      // Set the counter
    int result = 0;     // result

    printf("I'm thread[%d], start_num:%d, end_num:%d\n", my_num, start_num, end_num);

    /* find the prime number */
    for (i = start_num; i <= end_num; i++) {
        count = 0;      // Reset counter

        for (j = 1; j <= i; j++) {
            if (i % j == 0)
                count += 1;
        }
        
        if (count == 2) { 
            prime_array[my_num][k] = i;
            k++;
        }
    }


    // pthread_mutex_unlock(&work_mutex);
	pthread_exit(0);
}


static double getDoubleTime() {
        struct timeval tm_tv;
        gettimeofday(&tm_tv,0);
        return (double)(((double)tm_tv.tv_sec * (double)1000. + (double)(tm_tv.tv_usec)) * (double)0.001);
}

* [執行結果]

### (二) 加上 `pthread_mutex_lock()`、`pthread_mutex_unlock()`
* 在 `void *thread_function(void *arg) { ... }` 裡面的開頭和結尾分別加上 `pthread_mutex_lock(&work_mutex);` 和 `pthread_mutex_unlock(&work_mutex);`

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h> 
#include <time.h>

#define NUM_THREADS 10
#define MSIZE 100

// 找出 1 - 100 的所有質數

static double getDoubleTime();
void *thread_function(void *arg);
pthread_mutex_t work_mutex;


int main(void) {
	int res;
	pthread_t a_thread[NUM_THREADS];
	void *thread_result;
	int lots_of_threads;
	
	// start to measure time...
	double start_time = getDoubleTime();
	
	// initialize mutex...
	res = pthread_mutex_init(&work_mutex, NULL);
	if (res != 0) {
       	perror("Mutex initialization failed");
	    exit(EXIT_FAILURE);
    }

	// pthread_create...
	for (lots_of_threads = 0; lots_of_threads < NUM_THREADS; lots_of_threads ++) {
		res = pthread_create(&(a_thread[lots_of_threads]), NULL, thread_function, (void*)(long)lots_of_threads);
	
        if (res != 0) {
			perror("Thread creation failed");
        		exit(EXIT_FAILURE);
		}
	}

	// pthread_join...
	for (lots_of_threads = NUM_THREADS - 1; lots_of_threads >= 0; lots_of_threads--) {
        	res = pthread_join(a_thread[lots_of_threads], &thread_result);
    
            if (res != 0) {
	            perror("pthread_join failed");
        	}
    }	

	printf("\nThread joined\n");

	// stop measuring time...
	double finish_time = getDoubleTime();
	printf("Execute Time:  %.3lf ms\n", (finish_time - start_time));
    exit(EXIT_SUCCESS);
}


void *thread_function(void *arg) {
    pthread_mutex_lock(&work_mutex);
	
    int my_num = (long)arg;
	// if (MSIZE % NUM_THREADS != 0){    printf("error");   pthread_exit(-1);    }

    int start_num = (MSIZE / NUM_THREADS) * my_num + 1;
	int end_num = (MSIZE / NUM_THREADS) * (my_num + 1);

    int i = 0, j = 0;   // Set the loop
    int count = 0;      // Set the counter
    int result = 0;     // result

    printf("\n\nI'm thread[%d], start_num:%d, end_num:%d\n", my_num, start_num, end_num);

    /* find the prime number */
    for (i = start_num; i <= end_num; i++) {
        count = 0;      // Reset counter

        for (j = 1; j <= i; j++) {
            if (i % j == 0)
                count += 1;
        }
        
        if (count == 2) { 
            result = i;
            printf("%d\t", result);
        }
    }

    pthread_mutex_unlock(&work_mutex);
	pthread_exit(0);
}


static double getDoubleTime() {
        struct timeval tm_tv;
        gettimeofday(&tm_tv,0);
        return (double)(((double)tm_tv.tv_sec * (double)1000. + (double)(tm_tv.tv_usec)) * (double)0.001);
}

* [執行結果]

## 三、取質數的範例程式

#include <stdio.h>
#include <stdlib.h>

// 找出所有質數
int main(void) {
    int i = 0, j = 0;   // 設置雙層迴圈
    int count = 0;      // 設置計數器
    int result = 0;     // 結果
    int max_num = 100;        // 最大整數
    
    printf("%d 的質數有：\n", max_num);

    for (i = 1; i <= max_num; i++) {
        count = 0;      // 計數器歸0

     /* 當因數只有兩個，可以確認該整數為質數 */
        for (j = 1; j <= max_num; j++) {
            if (i % j == 0)
                count += 1;
        }
        
        if (count == 2) {
            result = i;
            printf("%d\t", result);
        }
    }

    printf("\n");
}