D言語でかく素数プログラム(エラトステネスの篩)
後輩に素数プログラムを書いてくださいと言われたので書いてみた
どうやら後輩はC言語を勉強中であり、C言語でとりあえずささっと実装した
1~100までの素数を出せばいいらしい
1分で作ったコード
#include<stdio.h> #include<math.h> #define N 100 int main() { int a[101] = { 0 }; int i, i2; for (i = 2; i <= (int)sqrt(N); i++) { for (i2 = i; i*i2 <= N; i2++) { a[i*i2] = 1; } } for (i = 2; i <= N; i++) { if (!a[i]) printf("%d\n", i); } }
アルゴリズム的には素数問題の解法でよく使われるエラトステネスの篩です。
2*2,2*3,2*4,,...10*10と倍数になるものは素数ではないので配列に目印立てとけばいいだけの話です
理論的な話は、Wkipediaを見てください
エラトステネスの篩 - Wikipedia
しかし、後輩からの一言に衝撃を受けた....
なんと配列をまだ習っていないという....
配列なしに素数を出すプログラムとは???と考え見つけ出したのがこれ
#include<stdio.h> int main() { int i, i2; for (i = 2; i<100; i++) { for (i2 = 2; i2 <= i; i2++) { if (i == i2) { printf("%d\n", i); } if (i%i2 == 0) { break; } } } }
いや~なんとも普通なプログラム....
若干高速化できないかと考えて
#include<stdio.h> #include<math.h> int main() { int i, i2; printf("2\n"); for (i = 3; i<100; i+=2) { int a = 1; for (i2 = 3; i2 <= sqrt(i); i2+=2) { if (i%i2 == 0) { a = 0; break; } } if (a) printf("%d\n", i); } }
とりあえず素数は奇数しかないので奇数だけループを回して考える
ちょっとは早い
最後にD言語で素数問題(エラトステネスの篩)を解いてみる(これがやりたかっただけ)
import std.stdio,std.math; const int N = 101; bool[N] a; void main() { for(int i=2;i<=sqrt(cast(double)a.length);i++){ for(int i2=i;i*i2<=a.length;i2++){ a[i*i2]=true; } } for(int i=2;i<a.length;i++){ if(!a[i]) writefln("%s",i); } }
まあ普通にC言語っぽい