Lonely Prime Number

 (圖文無關)

(image and content are no connection.This article has no English version)

(絵と文は関係ない。この記書は日本語じゃありません)

寫程式，可以是痛苦的有可以是快樂的

只要不是盲目的抄襲，或是完全的複製貼上

在事成之後，那一種滿足感是難以言喻的...

最近一陣子在寫平行程式這一門課的作業

我們要做的事情很簡單

寫一支找質數的程式

老師訂的題目是找1,000,000(一百萬)以內的質數

利用平行程式的寫法，來看加速的狀況如何

質數是孤獨的

質數就是除了自己本身和1以外沒有其他的因數

在一個固定範圍內找出全部質數的方法有很多種

像是倍數刪去法:

從小到大，把目前這項的倍數全部去掉，慢慢提高沒有被刪掉的基底數的值，值到全部跑完，剩下沒被刪掉的數即為質數

或是開根號檢查因數法:

把數字開根號，除以比跟號值要小的所有數字，如果都除不盡即為質數

另外還有很多很多的方法

因為不是念數學系或是對數論有太大的興趣，所以發法就簡單的說明到這邊

接下來就是實做程式部份

很快的，我就把倍數刪去法的數學步驟寫成了程式碼

這時遇上了問題

作平行化的時候各個子程序的最小基底數不一樣，會有刪不乾淨的問題

分到值域越後段的需要重複檢查越多次

換個作法，把大家的基底數都調到和第一區段一樣的開始作

會有數據需要同步多次的問題

煩惱了一個下午之後，這種方式要平行化有點超出我的有限時間

最後還是用老方法也就是大部分用的暴力解(開根號因數檢查法)

如果不敢時間的話，還滿希望可以用第一種演算法來做的

不過平行化之後恐怕不會加速還會減速呢...