100以下の素数を求める最短のプログラムに対抗してみた
| 問題：100以下の素数を全て表示する、最も効率の良いプログラムをつくってください。
回答：printf("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"); |
ってのがあったので、ちょっと対抗してみた ・ω・
| printf("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"); |
このコード、81bytes
| for(int i=100,j;--i>1;){for(j=i;--j>1;)j*=!!(i%j);if(j==1)printf("%d ",i);} |
できたコード 75bytes
簡単に解説
| for(int i=100,j;--i>1;){ |
取りあえず、100から1ずつ減らして2になるまで回す処理
| for(j=i;--j>1;) |
対象の数字を割るための変数設定
本来は SQRT(i)以下の数字で検証すればいいのだけど、短くするためにこうなりました
| j*=!!(i%j); |
割り切れた場合は 0を代入して処理を抜ける。それ以外は続行
!!とすることで(bool)したのと同じ効果が得られる
| if(j==1)printf("%d ",i); |
最後まで割り切れなかった場合は1になるので出力
小さい方から表示したいなら
| for(int i=1,j;i++<100;){for(j=i;--j>1;)j*=!!(i%j);if(j==1)printf("%d ",i);} |
こうするだけ ・ω・
Translate
とりあえず、j=iの前に”int “で79文字なのでは？
とりあえず、j=iの前に”int “で79文字なのでは？
for の中で定義してるので要らないですよ・ω・
for の中で定義してるので要らないですよ・ω・
失礼しました。
外側のfor文でiと一緒に宣言してるんですね。
失礼しました。
外側のfor文でiと一緒に宣言してるんですね。
68byte にまで縮めてみました。
for(long d=0x22534C96996DE,n=2;d>>=1;n+=1+n%2)d%2?printf(“%d “,n):0;
long が 64bit 以上で、C99 対応のコンパイラ
なら、大丈夫だと思います。
int が64bitな環境なら、後1byte減らせるのですが、64bit 環境といっても、int は32bit
ということが多いので、long にしてみました。
128以下の素数しか出せないので、
黒翼猫さんより汎用性はありませんが。
簡単な説明
d は、右から順に、1bit目は1, 2bit目は2,
3bit目は3, 4bit目は5, 5bit目は7, …
を意味し、
素数なら1, 素数でなければ 0 をセット
しています。(2進数に展開してみると分かりやすいでしょう)
あとは、右から順に各bit の値を見ていき、
素数だったら、画面に結果を出力しているだけです。
68byte にまで縮めてみました。
for(long d=0x22534C96996DE,n=2;d>>=1;n+=1+n%2)d%2?printf(“%d “,n):0;
long が 64bit 以上で、C99 対応のコンパイラ
なら、大丈夫だと思います。
int が64bitな環境なら、後1byte減らせるのですが、64bit 環境といっても、int は32bit
ということが多いので、long にしてみました。
128以下の素数しか出せないので、
黒翼猫さんより汎用性はありませんが。
簡単な説明
d は、右から順に、1bit目は1, 2bit目は2,
3bit目は3, 4bit目は5, 5bit目は7, …
を意味し、
素数なら1, 素数でなければ 0 をセット
しています。(2進数に展開してみると分かりやすいでしょう)
あとは、右から順に各bit の値を見ていき、
素数だったら、画面に結果を出力しているだけです。
CPUカウンタ考慮するとどっちが軽いのだろう。。
CPUカウンタ考慮するとどっちが軽いのだろう。。