吉田武「オイラーの贈物」「基礎理論(Basic Theory)」「素数と合成数」より
自然数において1とその数自身の他に約数（divisor）を持たない数を素数（prime number）という。そしてそれ以外の、すなわちいずれかの素数の積、すなわち倍数（multiple）として表現可能な、すなわち素因数分解（factorization into prime number）可能な数を合成数（composite number）という。
- 自然数２は唯一の偶数の素数であり、偶素数（even prime number）とも呼ばれる。
- 素因数分解は掛ける順番を考慮しないでよければ一意に定まる。これを素因数分解の一意性（uniqueness）という。
具体的な素数の求め方としてはエラトステネスの篩（ふるい、Eratosthenes's sieve）が素数を組織的に求める方法として現在なおも意味を保ち続けている。
エラトステネスの篩（ふるい、Eratosthenes's sieve）
①まずは最小の素数2で割り切れる数、すなわち2の倍数（multiple）あるいは偶数（even numbers）を除去する。かくして１を除く奇数だけが残る。
②残った数の先頭である3の倍数6,9,12…を除去する。
③これをガウスの記号（Gaus's symbol）すなわちNを超えない最大の整数[N]の平方根、すなわち[sqrt(N)]まで繰り返す。
統計言語Rでの検証
#上掲の定義に従って１を除いた奇数の自然数（上限100）から検討を開始する。
Evaluation_Target<-c(3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45, 47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99)
#この単元は100を最大数とするので[sqrt(100)]すなわち検討対象が10を超えたら検討を終了する。
Evaluation_Max<-c(10)
#開始時点で素数リストは2のみ
Prime_Number_List<-c(2)
#具体的検討過程①検討対象の先頭の数字を取り出す。まずは３が出てくる。
Current_Prime_Number<-Evaluation_Target[1]
Current_Prime_Number
[1] 3
#②取り出した数字が検討の上限を超えてたら検討終了。そうでなければ、取り出した数字を素数リストに追加してその倍数を検討対象リストから除去する。まずは上限以下のケースから開始。
Current_Prime_Number_List <-c(Prime_Number_List,Current_Prime_Number)
Current_Prime_Number_List
[1] 2 3
Natural_Number_Coefficient<-c(1:100)
Current_Multiple_Sequence<-Natural_Number_Coefficient*Current_Prime_Number
Current_Multiple_Sequence
[1] 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66
[23] 69 72 75 78 81 84 87 90 93 96 99 102 105 108 111 114 117 120 123 126 129 132
[45] 135 138 141 144 147 150 153 156 159 162 165 168 171 174 177 180 183 186 189 192 195 198
[67] 201 204 207 210 213 216 219 222 225 228 231 234 237 240 243 246 249 252 255 258 261 264
[89] 267 270 273 276 279 282 285 288 291 294 297 300
Current_Evaluation_list <- setdiff(Evaluation_Target, Current_Multiple_Sequence)
Current_Evaluation_list
[1] 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91
[31] 95 97#③次の検討対象の先頭の数字を取り出す。５が出てくる。
Current_Prime_Number<-Current_Evaluation_list[1]
Current_Prime_Number
[1] 5
#④繰り返す。
Current_Prime_Number_List <-c(Prime_Number_List,Current_Prime_Number)
Current_Prime_Number_List
[1] 2 3 5
Current_Multiple_Sequence<-Natural_Number_Coefficient*Current_Prime_Number
Current_Evaluation_list <- setdiff(Current_Evaluation_list, Current_Multiple_Sequence)
Current_Evaluation_list
[1] 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97
#⑤次の検討対象の先頭の数字を取り出す。７が出てくるので繰り返す。
Current_Prime_Number<-Current_Evaluation_list[1]
Current_Prime_Number
[1] 7
Current_Prime_Number_List <-c(Prime_Number_List,Current_Prime_Number)
Current_Prime_Number_List
[1] 2 3 5 7
Current_Multiple_Sequence<-Natural_Number_Coefficient*Current_Prime_Number
Current_Evaluation_list <- setdiff(Current_Evaluation_list, Current_Multiple_Sequence)
Current_Evaluation_list
[1] 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
#⑥次の検討対象の先頭の数字を取り出す。11が出てくる。検討の上限を超えたので検討中の素数リストに残りを加えて処理終了。Prime_Number_List<-c(Current_Prime_Number_List,Current_Evaluation_list)
Prime_Number_List
[1] 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
統計言語Rによる上掲プロセスの関数化
Prime_Number_Choosing<-function(Calculation_Max){
#「検討の上限」を準備する。
Evaluation_Max<-sqrt(Calculation_Max)#「１を除く奇数の数列」を準備する。
Allmost_Natural_number_list<-c(1:Calculation_Max) #1を除く
Odd_General_Term<-function(x){2*x+1}
Allmost_Odd_Sequence<-Odd_General_Term(Allmost_Natural_number_list)
Evaluation_Target<-Allmost_Odd_Sequence[Allmost_Odd_Sequence <= Calculation_max]#「最初の素数2のみが入った検討済み素数の数列」を準備する。
Prime_Number_List <-c("2")
#上掲処理を整理した抽出過程。
while(Evaluation_Target[1] <= Evaluation_Max){
Prime_Number_List <-c(Prime_Number_List,Evaluation_Target[1])
Current_Multiple_Sequence<-Allmost_Natural_number_list*Evaluation_Target[1]
Evaluation_Target <- setdiff(Evaluation_Target, Current_Multiple_Sequence)
}
Prime_Number_List<-c(Prime_Number_List,Evaluation_Target)
return(c(Prime_Number_List))
}
Prime_Number_Choosing(100)#25個
[1] "2" "3" "5" "7" "11" "13" "17" "19" "23" "29" "31" "37" "41" "43" "47" "53" "59" "61"
[19] "67" "71" "73" "79" "83" "89" "97"
#次の素数101はCalculation_Maxを10201以上に上げないと登場しない。しかも何故か計算エラーが…
Prime_Number_Choosing(10300)
while (Evaluation_Target[1] <= Evaluation_Max) { でエラー:
TRUE/FALSE が必要なところが欠損値です
とりあえず以下続報。
