2006/06/16
Document Actions
キミならどう書く 2.0 - ROUND 1 -
LL Ring の前哨戦として「キミならどう書く 2.0」の開催です！
今回は読者も参加しての大乱闘！！
お題は「100までの整数から素数を列挙せよ」です．
ぜひ，みなさんの解答をコメントやトラックバックでお寄せください！
解答の締切は6月26日（月）とします．締切後には投票による人気の集計を行います．
今回は読者も参加しての大乱闘！！
お題は「100までの整数から素数を列挙せよ」です．
ぜひ，みなさんの解答をコメントやトラックバックでお寄せください！
解答の締切は6月26日（月）とします．締切後には投票による人気の集計を行います．
- Category(s)
- キミならどう書く2.0
Pythonのジェネレータを使って素数を求める
Python 2.3から(だったっけな？)導入された「ジェネレータ関数」を使って素数を求めてみましょう。 >>> def primegen(x=2): # 素数を返すジェネレータ関数を定義 ... while True:...
perl - 100までの素数
なに前哨戦とな?
キミならどう書く 2.0 - ROUND 1 - ? Lightweight Language Ringお題は「100までの整数から素数を列挙せよ」です．
[プログラミング]Concurrent Clean : L.L.Ring : 『キミならどう書く 2.0 - ROUND 1 -』 : 100までの素数を列挙
module Primes import StdEnv, OptEnv Start = takeWhile ((>=) 100) primes primes = ps [2..] where ps [n:nr] = [n: ps $ filter (\x = (x rem n) <> 0) nr] たしか、もっとスマートな方法があったような気がするんだけど・・・
エラトステネスのふるい @ Ruby
コンセプトは「人と同じ動き」です．
人が紙に書いてエラトステネスのふるいで解いていくのと同じ流れのコードとなっています．
キミならどう書く 2.0 - ROUND 1 -
100までではちょっと上が小さすぎる。「最初の1,000,000個」とかに変更すべき。ここまで大きければHaskellでも素朴なsieveでは表示できなくなる(sieveはやがてメモリを喰い尽くして止まる。やってみればわかる)ので、腕の見せ所となる。
100までの素数＠ruby
なにやら面白そうな企画が開催されているようなので、乱入。「100までの素数を列挙するコードを書くべし」だそうです。とりあえずRubyを使って書いてみました。 def generate_prime_numbers(max) (2..max).inject([]) do |list, n| append_if_prime(list, n) end e..
「100までの整数から素数を列挙せよ」
http://ll.jus.or.jp/2006/blog/doukaku1 に「キミならどう書く 2.0 - ROUND 1 -」として「100までの整数から素数を列挙せよ」というお題が出ている。 ちゃんと計算するのは面倒なので「0ruby -r mathn -e '(1..100).select{|x|x.prime_division.size == 1}.join(" ").display'」で。 最初は1からではなく0からにしていたら、「0.prime_division」がかえってこなくて悩んでし ...
素数探索＠Ruby
キミならどう書く 2.0 - ROUND 1 -にて、「100までの整数から素数を列挙せよ」とのお題。 (2..100).select{|i|(2...i).all?{|j|i%j!=0}} とりあえず効率無視で短さ重視。 (2..100).select{|i|/^(11+)\1+$/!~'1'*i} と思ったら、perl - 100までの素数 にある
[Squeak][Smalltalk] 100までの整数から素数を列挙せよ…を Squeak の Smalltalk で
「100までの整数から素数を列挙せよ」：キミならどう書く 2.0 - ROUND 1 - ― Lightweight Language Ring まずはお約束から。 Integer primesUpTo: 100 #(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) 愚直に。 (2 to: 10) collect: [:nn | (2
エラトステネス/フェルマーテスト
LL Gong キミならどう書く 2.0 - ROUND 1 -
100までの素数列挙．
正攻法だとエラトステネスの篩いを使ってこんな感じ．
LLR2006 - 1,000,000(番目|まで)の素数
キミならどう書く 2.0 - ROUND 1 - ? Lightweight Language Ringお題は「100までの整数から素数を列挙せよ」です．
に対して
mputの日記。 - キミならどう書く 2.0 - ROUND 1 -100までではちょっと上が小さすぎる。「最初の1,000,000個」とかに変更すべき。ここまで....
[LL]キミならどう書く 2.0 - ROUND 1 6月26日（月）締切
いい感じでRSSからお題が送られてきました。（この記事は6/25(日)まで更新し続けます。) LL Ring の前哨戦として「キミならどう書く 2.0」の開催 お題は「100までの整数から素数を列挙せよ」です． 解答の締切は6月26日（月）とします．締切後には投票による人気の集計を行
Ruby標準添付ライブラリ - LL Ring
まずは、日本Rubyカンファレンス2006でネタにした関係上、お約束のやつだけ...
[ruby] キミならどう書く 2.0 - ROUND 1 -
お題は「100までの整数から素数を列挙せよ」。 via Yuguiさんとこ Rails厨の回答。 #!/usr/bin/env ruby require_gem 'activesupport' require 'active_support' class Fixnum def prime? return false if 1 == self (2..self - 1).all?{|i| (self % i) 
[PRO] Io で 100 までの素数を列挙
お題は「100までの整数から素数を列挙せよ」です． ぜひ，みなさんの解答をコメントやトラックバックでお寄せください！ キミならどう書く 2.0 - ROUND 1 - ? Lightweight Language Ring との事なので、力の差にしりごみしながらも参戦してみるテスト。 折角なので今勉強中
[OCaml] キミならどう書く 2.0 - ROUND 1 - — Lightweight Language Ring
お題は「100までの整数から素数を列挙せよ」です． MLならループ使ってなんぼでしょう。 愚直に。 # exception NotPrime;; exception NotPrime # begin for i = 2 to 100 do try for j = 2 to i / 2 do if i mod j = 0 then raise NotPrime done; Printf.printf "%d &q
[programming] お題は「100までの整数から素数を列挙せよ」
http://ll.jus.or.jp/2006/blog/doukaku1 にて，「キミならどう書く 2.0」というプログラミングスキルを競うコンテストが開催されているみたい．お題は「100までの整数から素数を列挙せよ」．面白そう． とはいえ，100までの素数なんて25個しかないのだから，いちいち計算せ
キミならどう書く 2.0 - ROUND 1 -
コンセプトは「人と同じ動き」です．人が紙に書いてエラトステネスのふるいで解いていくのと同じ流れのコードとなっています． エラトステネスのふるい @ Ruby - 32nd diary (2006-06-16) コンセプトは「人と同じ動き」です．人がググって検索上位のサイトを見てみるのと同
[Smalltalk][OOPL] 100までの整数から素数を列挙せよ…を Smalltalk-76 で
1977 年から、時空を越えてのエントリー。ｗ ”Smalltalk-76” limit ← 100. primes ← #() asStream. primes next ← 2. for% i from: (3 to: limit by: 2) do% [ isprime ← true. for% prime from: primes contents do% [ i ￥ prime = 0 ? [isprime ← false]]. ispri
[Ruby] キミならどう書く 2.0 - ROUND 1 -
LL Ringの前哨戦の「お題」がでていたので， 昔，勉強したフェルマーテストを使って，やってみました． a = 2 max = 100 range = Range.new(a, max) range.each{|num| if(a == num) then print num, " " elsif(1 == (a **(num - 1) % num)) then print nu
100 までの素数を列挙 in JavaScript
「キミならどう書く 2.0 - ROUND 1 - ― Lightweight Language Ring」より。せっかくなので JavaScript 1.7 の新機能である Generator を使って書いてみる。
function countUp(n)
{
n = n || 0;
while (true)
yield
素数列をつくろう
http://ll.jus.or.jp/2006/blog/doukaku1 面白そうなのでミラーテストバージョンを書いてみました http://www.faireal.net/articles/7/03/#d30129 このサイトを参考にしました。 実行結果
[プログラミング]Concurrent Clean : L.L.Ring : キミならどう書く 2.0 - ROUND 1 - 番外編：1,000,000個めの素数
チューニングとはCleanのための言葉です！！ かどうかは知りませんが、Cleanは、Haskellとは違ってプログラムを効率化するテクニックが多いので、数が多くなっても平気。 もともとの関数定義はこれ。 nth_prime n = primes !! n primes = map hd $ iterate f [2..] where f
[PRO] WhiteSpace でも 100 までの素数を列挙
「100までの整数から素数を列挙せよ」から色々な人のコードを見ていたら、 brainfuckやwhitespaceで作る人が出てこないかな. 他人のHaskell日記 なんてことを言っている人を発見。 了解です。できましたヽ(≧∀≦)ノ prime.ws 実行結果 $ perl whitespace.pl prime.ws 2 3 5
シェルで素数の列挙
こ、これはシェルでやるしかないでしょうってことでやってみた。
[IT]キミならどう書く 2.0 ROUND 1
お題は「100までの整数から素数を列挙せよ」です． キミならどう書く 2.0 - ROUND 1 - Lightweight Language Ring 世のビジネスシーンで最も多用されているアプリケーションの1つであるExcelのVBAマクロで書いてみよう。 Sub PrimeNum() Dim SUP As Integer: SUP = Cells(1,
[LL]キミならどう書く 2.0 - ROUND 1 6月26日（月）締切
いい感じでRSSからお題が送られてきました。（この記事は6/25(日)まで更新し続けます。) LL Ring の前哨戦として「キミならどう書く 2.0」の開催 お題は「100までの整数から素数を列挙せよ」です． 解答の締切は6月26日（月）とします．締切後には投票による人気の集計を行
[Squeak][Smalltalk] 100までの整数から素数を列挙せよ…を Smalltalk-72 で
悪ノリして、今度は 1974 年からのエントリー。 "limit _ 100. "primes _ stream of vector 1. primes _ 2. for i _ 3 to limit by 2 ("isprime _ true. "vec _ primes contents. for idx to vec length ("prime _ vec[idx]. (i mod prime) = 0? (
[プログラミング]Concurrent Clean : L.L.Ring : キミならどう書く 2.0 - ROUND 1 - 高速化編
id:lethevert:20060616:p2 : 素直な回答 id:lethevert:20060617:p1 : 頭部非ボックス化正格リスト id:lethevert:20060617:p2 : gccとの速度比較 ここまで、コードの外形には触れずにいましたが、コードの外形を変えて高速化してみましょう。 Start = last $ takeWhile ((
javascriptで素数生成
これをJavascriptで。
[http://ll.jus.or.jp/2006/blog/doukaku1:title]
*アルゴリズム
[g:素数判定 アルゴリズム]で探してみたけど、技術
[Groovy]キミならどう書く 2.0 - ROUND 1 -
Groovyで書いてみた。まずはこんな感じのコード。
println ((2..100).findAll{x->(2..x/2).every{x%it!=0}})
しかし、実行してみると、何故か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]
たぶん、範囲式の使い方が原因だろうということで、ちょっと調べてみる。
(2..1).each{println it}
=>
2
1
どうやら、(x .. y)で、x>yの場合は、空の範囲を生成するのではなく、x,
x-1,x-2,...,yの範囲を生成するようだ。しかも、Groovyの公式ページのドキュメントを見ても、この仕様に関するきちんとした記述が見当たらないorz
仕方無いので、内側のループは2..x/2ではなく、2...xにすることにした。
println ((2..100).findAll{x->(2...x).every{x%it!=0}})
今度は、ちゃんと2も出力されるようになった。
[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]
[Groovy]キミならどう書く 2.0 - ROUND 1 -
Groovyで書いてみた。まずはこんな感じのコード。
println ((2..100).findAll{x->(2..x/2).every{x%it!=0}})
しかし、実行してみると、何故か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]
たぶん、範囲式の使い方が原因だろうということで、ちょっと調べてみる。
(2..1).each{println it}
=>
2
1
どうやら、(x .. y)で、x>yの場合は、空の範囲を生成するのではなく、x,
x-1,x-2,...,yの範囲を生成するようだ。しかも、Groovyの公式ページのドキュメントを見ても、この仕様に関するきちんとした記述が見当たらないorz
仕方無いので、内側のループは2..x/2ではなく、2...xにすることにした。
println ((2..100).findAll{x->(2...x).every{x%it!=0}})
今度は、ちゃんと2も出力されるようになった。
[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]
100までの素数を求める
キミならどう書く 2.0 - ROUND 1面白そうなので参加。ハッシュを使ってみた。my $num = 100;my %a = map {$_, 1} 2..$num; for my $m (2..($num / 2)) { for my $n ($m..$num) {...
上限を決めずに素数を生成(JavaScript版)
JavaScriptでも書いてみた。
LL2006 君ならどう書く
LL2006の、「君ならどう書く」の読者参加版ができていた。 お題は 「100ま...
[Ruby] 100までの整数から素数を列挙せよ
お題は「100までの整数から素数を列挙せよ」です． 手垢がついた手法だと思うけど、Google 電卓で計算してみた。 ほんとは はてなのスーパー pre 記法拡張を使ってみたかっただけ。
[Squeak][Smalltalk][OOPL] エラトステネスのふるいをコンパクトにする方法
素数を列挙するにあたって、エラトステネスのふるいは比較的高速で、たとえば、404 Blog Not Found:LLR2006 - 1,000,000(番目|まで)の素数 で、いくつかの言語で例示されているのとほぼ同じことをする Squeak を使った Smalltalk の次のコード… [ | max primes isPrime | m
エラトステネスの篩の改良
上のソースでは探索範囲1つにつき true/false を作るので、1億まで探索しようと思うとかなりのメモリが必要となる。どうせ真偽値なのだから、BitArray を用いれば候補一つにつき 1bit で済む。また、偶数はどうせ素数ではないので、奇数のみを探索対象にすることで、テーブ
正規表現で素数探索
def sieve_regex(max) table = ' ' + (2..max).map{|i|i.to_s}.join(' ') (2..Math.sqrt(max)).each do |i| 1 while table.gsub!(/^((?:\d* ){#{i-1}}(?:(?:\d* ){#{i}})+)\d+/){$1} end table end perl -le ’$,=” ”; print grep {
上限を決めずに素数を生成の高速化(Ruby版)
「上限を決めずに素数を生成」を高速化。
[技術]せっかくだから素数数えとくか
決して落ち着きを取り戻すためにやってるわけではない*1．キミならどう書く 2.0 - ROUND 1 -ネタ． Otsuneのなんでこれで素数判定できるかは、読者の宿題のエラトステネスのふるいがステキだったのでうちもふるいを使いたいと思った．で，せっかくだから一気にふるいをかけ
[tech]数を数えて落ち着くんだ(Pnuts編)
キミならどう書く 2.0 Pnutsでできる限り簡潔、効率無視で書いてみた。 isPrim = function(p) {list(range(2,p)[function(d) p%d == 0]).size()==1} for(i: range(2, 100)[isPrim]) print(i,",") [実行結果]: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
100までの整数から素数を列挙せよ(Mathematica)
キミならどう書く 2.0 - ROUND 1 -から Select[Range@...
100までの素数を求める[APL版]
キミならどう書く 2.0 - ROUND 1APL版も作成してみた。(ただし、このアルゴリズムは昔に本で読んだもので、僕が考えた訳ではない)1～Xまでの数列を...
100までの整数から素数を列挙せよ(LaTeX)
\documentclass{jarticle} \newif\ifprime ...
100までの整数から素数を列挙 in Io :-|
キミならどう書く 2.0 - ROUND 1 -
というものが開催されていたことに遅ればせながら気がついたので、
Ioの思い出しを兼ねてやってみた。
(HaskellとかJavaScriptはほかの人がやっていたし)
最も簡単なパターンは、出力しちゃうこと。(ズル)write("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")Ioではprintはオブジェクトへのメッセージなので、
こういう場合はwr...
キミならどう書く 2.0 - ROUND 1 - 100までの整数から素数を列挙せよ@AppleScript
キミならどう書く 2.0 - ROUND 1 -— Lightweight Language Ringより。やっぱり俺が書くならAppleScriptだろうてことで書いてみた。基本はエラトステネスの篩なんだが、AppleScriptでリストを扱うとき、追加するのは簡単だけど取り除くのが面倒くさい上に遅くなるし、100じゃなくもっと多いときは死ぬほど遅くなる(主に最初のリストを作る時点で)ので、『素数リストと探索リスト』ではなく『素数リストと除外リスト』を作り、素数リストの最大値の二乗が探索リストの最大値を超えたら、(素数リストの一番最後の数+1)〜100から除外リストにある数字を除外して終了。なんつーか素朴だなぁw
上限なしで素数生成(ML版)
さらに、ML(mosml)でやってみた。
100までの整数から素数を列挙せよ(XSL)
<?xml version="1.0" encoding="UTF-8" ...
[PHP]PHPな応募ないすね
キミならどう書く 2.0 - ROUND 1 - — Lightweight Language Ring でPHPな応募がない件について。(TB全部見てないので、もしあったらごめんなさい) ということでいっちょ書いてみました。 アルゴリズムに凝るのは苦手だし、ワンライナーは端からPHPに向いてないのであ
100までの素数を数えるサンプル
PHPkoyhogeLightweight Language Ring100PHPkoyhogePHP5
[neta] FORTRANで書いて、100台のスパコンにそれぞれ自然数を割り振って、素数かどうかを判定させた結果を返してもらうというのはどうか
PHPで素数判定
LL Ring の前哨戦として「キミならどう書く 2.0」の開催です！ 今回は...
100までの整数から素数を列挙せよ(SQL)
SELECT n as prime FROM( SELECT n,COUNT...
[Squeak] 100までの整数から素数を列挙せよ…を Squeak の eToys で
eToys でも id:squeaker さんの Kedama（毛玉）を使って書いてみました。Kedama は、端的には、複数のタートルを使って描くタートルグラフィックス・システムです。 Kedama: A massively-parallel tile-scriptable particle system Yamamoto さんのチュートリアルがわかりや
[Coding] 100までの素数＠XQuery
declare function prime($i as xs:integer) as xs:boolean
{
every $div in (2 to $i - 1) satisfies $i mod $div != 0
};
for $i in (2 to 100)
return if(prime($i)) then $i else ()
XQueryだとこんな感じでしょうか。しょぼーん(´・ω・｀)
[OCaml] キミならどう書く 2.0 - ROUND 1 - (L.L.Ring)
スレッドを使ったネタバージョン (言語は OCaml)
1〜100までの素数表示
http://ll.jus.or.jp/2006/blog/doukaku1 ary = (2..100).to_a ary.each do |m| ary.delete_if do |n| m != n && n % m == 0 end end p ary 参加資格とか特にないよね？ 特に面白いのも思いつかず。既に誰かが書いてそうな気はしたけど（未確認）、書いてみた。
[PHP] 100までの素数
<?php $max = 100; $arr = range( 2, $max ); $end = sqrt( $max ); for ( $i = 2; $i < $end; ++$i ) { if ( in_array( $i, $arr ) ) { $arr = array_filter( $arr, create_function( '$v', 'return $v % ' . $i . ' || $v === ' . $i . &
[Ruby] キミならどう書く 2.0 - ROUND 1 -
フェルマーテストに引き続き，エラトステネスの篩もやってみました． エラストテネスの篩では，検証する数の平方根まで比較すれば， 素数か非素数かの判定は十分といえます． prime = Array.new() max = 100 i = 2 while i <= max @flag = true prime.each{|num| if Mat
[Perl]100までの素数(mapと正規表現で)
遅ればせながら参戦 for my $i (2..100) { my $n = join ",",map{$i%$_} 2..$i-1; if($n !~ /^0\,/ && $n !~ /\,0/){ print "$i \n"; } } mapと正規表現で作ってみました。
Javaで素数を100万個求める
LL Ringの素数の話が盛り上がっている。 http://ll.jus.or.jp/2006/blog/doukaku1 Javaで参戦しようかと思ったがネタにも走れず、かといって短さにも走れず、速さだけなら前回のたらいの2番煎じになってしまう。 芸が無いので今回は見てるだけにしようと思った。 しかし色々
[prog] キミならどう書く 2.0 - ROUND 1 -
Befungeで書いてみました。
>v >125*25*pv
v < > v
>25*25*g 1+:25*`|
> v
>:25*25*p >25*25*g + :55*4*`|
^ <
^ <
>:::25*%\25*/p ^
>25*,@ ^ <
v <
>0>1+:55*4*`| v <
> ^ >::25*%\25*/g 48*-|
>:.v
^ < <
yhara@cosmos:~/src/befunge % ./a.out primes.bf
Befunge-93 Interpreter/Debugger v2.12
2 3 5 7 11 13 17 19 23 29 31 32 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Befungeについては、こちらを参照。
自分で動かしてみたいという奇特な方は、http://quadium.net/funge/downloads/ から処理系(Cのソースコードと、Windows用EXE入り)を入手してください。
[Perl] 100までの素数 (キミならどう書く 2.0 - L.L. Ring)
http://ll.jus.or.jp/2006/blog/doukaku1/ http://d.hatena.ne.jp/t-akihito/20060625/1151227410 LL Ring のチケット発売今日からだ。買ってこなくちゃ。 List::MoreUtils から all と before_incl を使って、リスト操作っぽく書いてみた。List::MoreUtils は標準モジュー
Brainf*ckで100までの素数を列挙してみるテスト
キミならどう書く 2.0 - ROUND 1 - LL Ring の前哨戦として...
[Perl][pugs] 100までの素数 Perl6 / pugs 版
Perl6 (pugs) で動くようにしてみた。 #!/usr/bin/pugs my $max = @*ARGS.pop || 100; my @primes = (2); for (3..$max) -> $n { @primes.push($n) if @primes.before_incl:{ sqrt $n <= $_ }.all:{ $n % $_ }; } @primes.join(' ').say; sub all (@lis
キミならどう書く 2.0 - ROUND 1
おおっと、今知りました。(via 竹迫さん) キミならどう書く 2.0 - R...
キミならどう書く 2.0 - ROUND 1
Pythonでdefもifもwhileもforも使わずに1行(126文字)で作...
100までの素数（キミならどう書く 2.0 - ROUND 1 -）
もう遅いか。うち着いたの４５分ぐらいだもんな。。。 ルートｎが必要だと思って、mathn.rb のヘルプ見たら、素数もあるじゃん。 あるものは使えばいいのさってことで、ヘルプそのまま。 require 'mathn' pp = Prime.new; pp.each {|x| break if x >...
print "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";
問題： これを期待通りに実行できる言語をあげよ。
解答例: Perl, Ruby, Python, AWK
def primegen(maximum):
v = range(2, maximum)
while v:
p = v[0]
v = filter(int(p).__rmod__, v)
yield p
# grrr, 圧倒的にPythonに不利な設定ですね！
def primegen(maximum):
v = range(2, maximum)
while v:
p = v[0]
v = filter(int(p).__rmod__, v)
yield p
Pythonで、スライスと集合をむりやり使ってみる
MAX = 100 + 1
multiples = []
for n in range(2, MAX):
multiples.extend(range(0, MAX)[2*n:MAX:n])
print set(range(2, MAX)) - set(multiples)
Pythonです。。
[p for p in range(2,100) if 0 not in [p%d for d in range(2,p)]]
sieve (p:ps) = p:sieve [q|q<-ps,q`mod`p/=0]
take 100 $ sieve [2..]
面白そうなのでついカッとなってC++テンプレートで書いてみました。
コードが長くなってしまったので自分のページの↓のURLに置いておきます。
http://www.3jikai.to/mzk/junk/prime.cpp
C++はLLじゃないと言われそうだけど、
実行がLightWeightなバイナリを吐けるLanguage
ということで勘弁してください。
Gaucheで。
(use srfi-42)
(list-ec(: n 2 101)(if(not(any?-ec(: j 2 n)(zero?(modulo n j)))))n)
トラックバックできないので、コメントにて失礼
http://nyaos.org/d/?p=(2006.06.17)
あえて、LL でない言語で挑戦。その分、ひねり成分不足
ある意味最も軽量な言語であるアセンブラで書いてみました。以下のURLからソースを取得できます(Linux, FreeBSD, MacOSXで確認)。
http://homepage.mac.com/naoki.koguro/prog/prime.s
なお、コンパイルは
% gcc -o prime prime.s
として、実行確認はgdbを使って
% gdb prime
(gdb) break b
(gdb) run
(gdb) x/100bd &prime
としてください。
小飼さんのところの以下のページを参考に awk で記述してみました。
http://blog.livedoor.jp/dankogai/archives/50534572.html
長いので、以下の URL に速度比較も含めて書きました。
http://gauc.no-ip.org/wiki.cgi/private?page=Blog%2F2006%2D6%2D17
昔ながらのBASICで。
すぐに使える実行環境が無いので机上デバッグしかしていません。
10 'SAVE "PRIME.BAS"
20 DIM A(100):I=2
30 FOR P=I*2 TO 100 STEP I:A(P)=1:NEXT P
40 I=I+1:IF I=101 THEN GOTO 60
50 IF A(I)=0 THEN GOTO 30 ELSE GOTO 40
60 FOR I=2 TO 100
70 IF A(I)=0 THEN PRINT I," ";
80 NEXT I
間違って、トラックバックを2回送ってしまいました。すみません。
filter() { read p && ( echo $p; awk "\$1 % $p != 0" | filter ) }
seq 2 100 | filter
#seqやawkを使うのはズルかもしれませんが、どうせshだとexprやtestも外部コマンドなわけだし．．．
#zshやbashの拡張機能を使うのと同程度のズルですよね。
filter (\x -> (product [1..x-1]+1) `mod` x == 0) [2..100]
filter(lambda i:reduce(lambda x,y: x*(i%y), range(2,i), 1), range(2, 100))
lispの解が少ないので、Common Lispで。
xyzzyでも動作します。
(defun loop-generate-primes (n)
"ループ版"
(let ((prime '()))
(push 2 prime)
(do ((x 3 (+ x 2)))
((> x n))
(if (dolist (i prime t) (if (zerop (rem x i)) (return nil)))
(push x prime)))
(nreverse prime)))
(defun recursive-generate-primes (limit)
"再帰版"
(labels ((check (x prime)
(cond ((endp prime)
t)
((zerop (rem x (car prime)))
nil)
(t
(check x (cdr prime)))))
(main (n x prime)
(cond ((> x n)
(nreverse prime))
((check x prime)
(main n (+ x 2) (cons x prime)))
(t
(main n (+ x 2) prime)))))
(main limit 3 (list 2))))
エラトステネスの篩のようなもので非効率的に素数を列挙します
n=100;for i in `seq 2 $n`;do for j in `seq $i $i $n`;do echo $j;done;done|sort -n|uniq -c|egrep '^ *1[^0-9]'|sed 's/.*[ \t]//'|xargs printf '%d ';echo ''
効率無視 Haskell版と同じくウィルソンの定理を使った PHP版
for ($i = 2; $i <= 100; $i++) if (gmp_mod(gmp_fact($i-1), $i) == $i-1) echo "$i\n";
gaucheの遅延ストリームでオーソドックスふるいをつかって。
長い。
(use util.stream)
(define ones (stream-cons 1 ones))
(define (add-streams s1 s2) (stream-map + s1 s2))
(define integer (stream-cons 1 (add-streams ones integer)))
(define prime-stream
(let loop ((primes (stream-cdr integer)))
(stream-cons (stream-car primes)
(loop
(stream-filter
(lambda (x)
(not (= (remainder x (stream-car primes)) 0)))
primes)))))
(let loop ((stream prime-stream))
(if (> 100 (stream-car stream))
(cons (stream-car stream) (loop (stream-cdr stream)))
'()))
javaで作成してみました。
public static void main(String[] args) {
int[] s = new int[100];
int x = 0;
boolean bool = false;
for(int i = 1; i <= 100; i ++) {
bool = false;
for (int k = 0; k < x; k++) {
if (i % s[k] == 0 && s[k] != 1) {
bool = true;
break;
}
}
if (!bool) {
s[x++] = i;
System.out.println(i);
}
}
}
seq 2 100 | factor | awk 'NF == 2 {print $2}'
# 短さで勝負。GNU coreutils + awk を使用。
-- Lua
a={}
for i = 2, math.sqrt(100), 1 do
for j = i + i, 99, i do
a[j] = 1
end
end
for i = 2, 99, 1 do
if not a[i] then
print(i)
end
end
m4 で書いてみたです。
http://ya.maya.st/d/200606c.html#s20060626_1