アを１とする アに２を足す アに３を足す # # ... ひたすら続ける # アに１００００を足す アを出力するです。が、これだとプログラムが１０００１行も必要です。コーディングが大 変だし、書き損なう可能性もあります。
アを０とする １００００までのそれぞれについて繰り返す アにそれを足す アを出力する
1+ 2+ 3+...+ 9998+ 9999+10000
+10000+ 9999+ 9998+...+ 3+ 2+ 1
----------------------------------------
10001+10001+10001+...+10001+10001+10001
となり、10001 が 10000 個あることになります。これが、1から10000
までの数の２倍だったわけなので、求める数は
10001x10000/2 = 50005000となります。これは100まででも100000 でも一緒で、要するに最後の数と、最 後の数に１を足したものを掛けて２で割ればよいので、プログラムとしては以 下になります。
アを１００００とする イをアとする イに１を加える アにイを掛ける アを２で割る アを出力する
ちなみにこれはガウス が小学生のときに求めたという逸話で有名（実際 は微妙に違うという説 もあり）です。等差数列の和の公式でもあります。繰り返しの場合、１万までの和を求めるには１万回の足し算が必要ですが、上 の場合、いくつまでの和でも５回の計算ですむので計算の量としてはすごく効 率がよいわけです。このような、 効率のよい手順 （を考えること） が、すなわちアルゴリズムなわけです。
ハイレツを【５、６、９、２、７、３、８、１、４】とする ナガサを ハイレツの長さとする ＃空白を挟む（！） ０以上ナガサ未満のそれぞれをアとして繰り返す イを１とする イにアを足す イ以上ナガサ未満のそれぞれをウとして繰り返す もしハイレツのア番目がハイレツのウ番目以下ならば ハイレツのア番目とハイレツのウ番目を交換する ０以上ナガサ未満のそれぞれをアとして繰り返す ハイレツのア番目を出力するこのプログラムは２重のループ＝繰り返しになっていることが分かると思いま す。「ア」は外側の、「ウ」は内側のループのカウンタ＝今、配列のどの要素 を操作しているかを覚えておく変数です。「イ」は、アの１つ次を示していま す。
一番最初の時には、「ア」は０番目、「イ」は１番目、「ウ」も１番目です。 そして、「ウ」は繰り返すたびにカウントアップ＝１づつ増えていって、 ハイレツのア番目とハイレツのウ番目を比べて、ア番目が小さければ ア番目とウ番目を入れ替えています。つまり、配列の最初は
【５、６、９、２、７、３、８、１、４】ですが、この５と、そのあとの数字を比べて小さければ大きいものと交換する ので、１回目には
【６、５、９、２、７、３、８、１、４】
となり、次には
【９、５、６、２、７、３、８、１、４】となり、あとの 2,7,3,8,1,4 は９より小さいので 交換しません。つまり、最初のループで、この配列の中で 一番大きな数字を一番左（０番目）に置きました。結果として 配列は
【９、５、６、２、７、３、８、１、４】
となっています。
ここで、「ア」を１つ増やします。すなわち、配列の一番左は配列全 体の中で一番大きなものであることが決まっているので、その次に大きい ものを探しにいく、ということです。そうすると、次のループが終わった ときには、
【９、８、５、２、６、３、７、１、４】となり、これを繰り返すわけですので
【９、８、７、２、５、３、６、１、４】 【９、８、７、６、２、３、５、１、４】 【９、８、７、６、５、２、３、１、４】 【９、８、７、６、５、４、２、１、３】 【９、８、７、６、５、４、３、１、２】 【９、８、７、６、５、４、３、２、１】と交換がすすんで最後まで行って終了、となります。 このバブルソートの場合、９つの要素に対して比較（と、必要に応じて）並び 替えをするので、8+7+6+5+4+3+2+1 = 9*8/2 回の処理が必要となります。要素 が少ないときは問題にはなりませんが、要素が多いと、その ２乗程 度 の計算量が必要となり、かなり効率が悪いです。
この「２乗程度」のような計算量の 次数 のことを 「オー ダー」 と呼び、O(n2) のように記述することがあります。
関数クイックを引数ハで定義する ナガサを ハの長さとする ＃空白を挟む（！） もしナガサが１以下ならば ハを返す ではなくナガサが２と同じならば もしハの０番目がハの１番目以下ならば ハの０番目とハの１番目を交換する ハを返す ではなければ ナガサを２で割る ナガサを整数にする ナカをハのナガサ番目とする ダイを空配列とする ショウを空配列とする ハのそれぞれをアとして繰り返す もしアがナカより大きいならば ダイにアを付け足す ではなくアがナカと違うならば ショウにアを付け足す カエリを関数クイックを引数ダイで呼び出したものとする カエリにナカを付け足す カエリに関数クイックを引数ショウで呼び出したものを合わせる カエリを返す # ハイレツを【５、６、９、２、７、３、８、１、４】とする カエリチを関数クイックを引数ハイレツで呼び出したものとする カエリチを出力するクイックソートは、名前の通り早くソートすることが可能なソートアルゴ リズムです。特に要素が多い時に効果を発揮します。クイックソートは、 再帰関数の形で定義されます。再帰関数とは、自分の定義の中に自分が入っ ていて呼び出される（これが再帰呼び出し）関数のことです。
まず、データは
【５、６、９、２、７、３、８、１、４】要素数は9でランダムに並んでいます。 これをクイックソートを使用して降順にソートします。 まず、この9個の要素の中からひとつの要素を選びます。 ここでは、要素数の中間の値であるものを選びます。 コードにすると、
ナガサを２で割る ナガサを整数にする ナカをハのナガサ番目とするつまり、配列の長さの半分ですから、最初は４、だけど０から始まってるので ５番目の要素が中間値となります。つまり、７です。そして、この７を基準値 にしてデータ数列をソートしていきます。ちなみにこの基準値、つまり軸とな るものをピボットと呼びます。
【５、６、９、２、７、３、８、１、４】
次に、このピボットより大きいものと小さいものに分類します。
その受け皿用の変数として「ダイ」と「ショウ」を用意します。
そして、データ数列の先頭からピボットと比較して、
大きいものは「ダイ」に、小さいものは「ショウ」に付け足していきます。
最初のチェックでは、以下のようになります。
ダイ=【９、８】 ショウ=【５、６、２、３、１、４】そして、以下のようにそれぞれに対して「クイック」を適用します；
カエリを関数クイックを引数ダイで呼び出したものとする カエリにナカを付け足す カエリに関数クイックを引数ショウで呼び出したものを合わせる「ダイ」については、
【９、８】の２つだけですから
ではなくナガサが２と同じならば もしハの０番目がハの１番目以下ならば ハの０番目とハの１番目を交換する ハを返すを適用して、ここでのソートは終了です。その結果、データは変らず「カエリ」（深さ１）は以下です。
【９、８】そしてこれに後で「ナカ」を付け足して、さらにこれに「ショウ」をソートし た結果を付け足すわけです。すなわち；
【５、６、２、３、１、４】についてクイック（深さ２）を適用すると、ピボットが３になり、分類すると
ダイ=【５、６、４】 ショウ=【２、１】になります。この「ダイ」に再度クイック（深さ３）を適用すると、
ダイ=【】 ショウ=【５、４】となりますので、クイック（深さ３）のカエリは
【】＋６＋【５、４】=【６、５、４】になります。よって、クイック（深さ２）のカエリは
【６、５、４】＋３＋【２、１】=【６、５、４、３、２、１】となります。 さらに、これをカエリ（深さ１）に付け足すので、最終結果は以下になります；
【９、８】＋７＋【６、５、４、３、２、１】=【９、８、７、６、５、４、３、２、１】
以上のようにソートしていけば、降順にソートされることがわかります。今回 は、ピボットを真ん中の値としましたが、ソートに関して、効率のよい値をピ ボットにするのが細かい工夫になります。
クイックソートの場合、平均的にO(n・log(n)) の計算量である ことが知られています。バブルソートのO(n2) と比 べると、n が大きい場合はクイックソートのほうが圧倒的に有利 です。例えば、n=10000 の場合、
n2=100000000 (108)
ですが、
n・log(n) = 10000・log210000 ≒ 1.3・105
くらいなので、800倍近くの速度差になります。
＃ エラトステネスのふるい
＃
サイダイを百とする
リミットをサイダイの平方根とする
０以上サイダイ未満をハイレツに入れる
ハイレツの１番目を０とする
ハイレツのそれぞれをアとして繰り返す
もしアが０と同じならば
続ける
ではなくアがリミット以上ならば
抜ける
そうじゃなければ
イにアを入れる
イに２を掛ける
イからアおきにサイダイ未満のそれぞれをウとして繰り返す
ハイレツのウ番目を０とする
ハイレツのそれぞれをアとして繰り返す
もしアが０と違うならば
アを改行出力する
いま、国から 研究費を貰っているのですが、自分としては↑が動いてい るというのが決め手になったんじゃないかと思っています。これは、素数ではないデータを篩にかけて落していって、残ったものが素数で ある、という処理をしています。じっくり読んでみてください。