最近は、ちょっとプログラミングの話題が多いかな。
今回は、枝刈りについて考えてみようかと思う。
昨日の互いに素の記事では、画期的な方法で枝刈りをしてみました。
今日の題材は、素数とします。
素数も私のブログではよく出てくるものですが、今一度説明しましょう。
素数とは、1と自分自身しか約数を持たない数です。
例を挙げると、2、3、5、7、11、13、17、19、…と無限に存在することが証明されています。
ある自然数nが素数であるか判定するには、nより小さい自然数で割り切れなければ良いということ。
今回はサンプルが多くなるので、プログラム全体ではなく、素数判定ルーチンだけを考えます。
int check(unsigned int n)
で、判定したいnを与え、素数なら1、素数でないなら0を返すサブルーチンとします。
【サブルーチン1】
int check(unsigned int n)
{
unsigned int i;
for (i=2; i<n; i++) {
if ( n%i == 0 ) return 0;
}
return 1;
}
まったく枝刈りをしていない状態です。
これをベースに、どの様な枝刈りを思いつくでしょうか？
終了判定のi<nはかなり無駄で、i<=sqrt(n)に相当するものでよい。
【サブルーチン2】
int check(unsigned int n)
{
unsigned int i, j;
j = sqrt((double)n)+1;
for (i=2; i<j; i++) {
if ( n%i == 0 ) return 0;
}
return 1;
}
かなり枝刈りされましたが、まだまだ枝刈りの余地はあります。
因みに、
for (i=3; i<=sqrt((double)n); n+=2) { ... }
のようにしてはダメです。
何故かと言うと、終了判定で毎回sqrtを計算しなくてはならないからです。
2以外の素数は全て奇数。
【サブルーチン3】
int check(unsigned int n)
{
unsigned int i, j;
j = sqrt((double)n)+1;
if ( n%2 == 0 ) return 0;
for (i=3; i<j; i+=2) {
if ( n%i == 0 ) return 0;
}
return 1;
}
大抵の人は、このくらいまで枝刈りをします。
もっと枝刈りを増やしてみる。
【サブルーチン4】
int check(unsigned int n)
{
unsigned int i, j;
j = sqrt((double)n)+1;
if ( n%2 == 0 || n%3 == 0 ) return 0;
for (i=5; i<j; i+=6) {
if ( n%i == 0 || n%(i+2) == 0 ) return 0;
}
return 1;
}
【サブルーチン5】
int check(unsigned int n)
{
unsigned int i, j;
j = sqrt((double)n)+1;
if ( n%2 == 0 || n%3 == 0 || n%5 == 0 ) return 0;
for (i=7; i<j; i+=30) {
if ( n%i == 0 || /* 7 37 67 97 ... */
n%(i+ 4) == 0 || /* 11 41 71 101 ... */
n%(i+ 6) == 0 || /* 13 43 73 103 ... */
n%(i+10) == 0 || /* 17 47 77 107 ... */
n%(i+12) == 0 || /* 19 49 79 109 ... */
n%(i+16) == 0 || /* 23 53 83 113 ... */
n%(i+22) == 0 || /* 29 59 89 119 ... */
n%(i+24) == 0 ) { /* 31 61 91 121 ... */
return 0;
}
}
return 1;
}
サブルーチン3、4、5は、for文でi+=2、i+=6、i+=30と増えていき、if文の項数は1、2、8個と変化している。
表にまとめると、
| if文の項数 | for文の追加数 | 枝刈り率 |
| 1 | 2 | 50.0000000000% |
| 2 | 6 | 66.6666666667% |
| 8 | 30 | 73.3333333333% |
| 48 | 210 | 77.1428571429% |
| 480 | 2310 | 79.2207792208% |
| 5760 | 30030 | 80.8191808192% |
| 92160 | 510510 | 81.9474643004% |
| 1658880 | 9699690 | 82.8975977583% |
| 36495360 | 223092870 | 83.6411804644% |
| 1021870080 | 6469693230 | 84.2052776898% |
| 30656102400 | 200560490130 | 84.7147848611% |
| 1103619686400 | 7420738134810 | 85.1278987838% |
| 44144787456000 | 304250263527210 | 85.4906329598% |
| 1854081073152000 | 13082761331670030 | 85.8280601003% |
| 85287729364992000 | 614889782588491410 | 86.1295907364% |
| 4434961926979584000 | 32589158477190044730 | 86.3912965716% |
| 257227791764815872000 | 1922760350154212639070 | 86.6219525619% |
| 15433667505888952320000 | 117288381359406970983270 | 86.8412648150% |
| 1018622055388670853120000 | 7858321551080267055879090 | 87.0376638476% |
| 71303543877206959718400000 | 557940830126698960967415390 | 87.2202319624% |
こんな表が出来上がる。
いくらでも増やしていけるが、どこまで現実的かは、それぞれの判断に委ねることにする。
この表の規則性が解ると面白いかもしれません。
それこそ、この表を作らせる課題とかもいいかもしれません。
15行までならば、64ビットで計算出来ますね。
もっとやるなばら、多倍長演算を実装するとかしないとね。
ではでは