【雑談？】素数を求める。

[fulls]

部活中に友達とこんなことをしました。

C/C++でif,while,switch,forを使わずに1から1000までの素数を求めるプログラムを書く。

結局私も友達もできなかったのですが....

因みに私は関数のポインタ等をバンバン使って仕方なくgotoも使ってやろうとしました。
で、こんなトピックをたてたら面白いかなーと思いたてて見ました。
皆さん挑戦してくださいm(_ _)m

オフトピック

答えがあるなら見てみたいので..

[みけCAT]

ifが使えなければ、&&とか||とか?:とかを使えばいいじゃない。
コードゴルフやショートコーディングでは基本ですよ。

コード:

#include <stdio.h>

int is_sosuu(int target,int now) {
	return target<2?0:now>=target?1:target%now?is_sosuu(target,now+1):0;
}

int get_sosuu(int now,int max) {
	is_sosuu(now,2)&&printf("%d\n",now);
	return (now<max)&&get_sosuu(now+1,max);
}

int main(void) {
	get_sosuu(1,1000);
	return 0;
}

[みけCAT]

別のアプローチです。

コード:

#include <stdio.h>

const char* format="%d\n";

int main(void) {
	asm volatile (
		"pushl %ebp\n\t"
		"movl %esp,%ebp\n\t"
		"pushl %esi\n\t"
		"pushl %ebx\n\t"
		"movl $1,%ebx\n\t"
		"L15:\n\t"
		"cmpl $1,%ebx\n\t"
		"movl $2,%ecx\n\t"
		"setg %dl\n\t"
		"andl $255,%edx\n\t"
		"cmpl %ebx,%ecx\n\t"
		"movl %edx,%esi\n\t"
		"jge L9\n\t"
		"L13:\n\t"
		"movl %ebx,%edx\n\t"
		"movl %ebx,%eax\n\t"
		"sarl $31,%edx\n\t"
		"idivl %ecx\n\t"
		"testl %edx,%edx\n\t"
		"je	L19\n\t"
		"incl %ecx\n\t"
		"cmpl %ebx,%ecx\n\t"
		"jl	L13\n\t"
		"L9:\n\t"
		"testl %esi,%esi\n\t"
		"jne L20\n\t"
		"L6:\n\t"
		"incl %ebx\n\t"
		"cmpl $999,%ebx\n\t"
		"jle L15\n\t"
		"leal -8(%ebp),%esp\n\t"
		"popl %ebx\n\t"
		"popl %esi\n\t"
		"popl %ebp\n\t"
		"jmp L21\n\t"
		"L20:\n\t"
		"pushl %eax\n\t"
		"pushl %eax\n\t"
		"pushl %ebx\n\t"
		"pushl _format\n\t"
		"call _printf\n\t"
		"addl $16,%esp\n\t"
		"jmp L6\n\t"
		"L19:\n\t"
		"xorl %esi,%esi\n\t"
		"jmp L9\n\t"
		"L21:\n\t"
	);
	return 0;
}

[bitter_fox]

既にCで出てるので別の言語で・・・
Scalaです。

コード:

object Main
{
	def isPrime(n : Int) : Boolean = n >= 2 && (2 to n).count(n % _ == 0) == 1

	def main(args : Array[String]) : Unit = (2 to 1000).filter(isPrime).foreach(println);
}

[hr][編集]filter().size()をcount()に変更

[追記]
カロさんのコードの様にisPrimeを簡潔にできた。

コード:

object Main
{
	def isPrime(n : Int) : Boolean = (2 to n - 1).forall(n % _ != 0)

	def main(args : Array[String]) : Unit = (2 to 1000).filter(isPrime).foreach(println);
}

n to mでn > mの時は空のRangeが作成されるのか・・・

[みけCAT]

質問に「C/C++で」と明記されています。

C++で書いてみました。

コード:

#include <cstdio>
#include <algorithm>

int slist[1000];

int suuti_gen(void) {
	static int suuti=1;
	return suuti++;
}

class sosuu_hantei {
	private:
		int number;
		int ok;

	public:
		sosuu_hantei(int num) : number(num) , ok(1) {}
		void operator() (int x) {ok=ok && (number%x);}
		int get_result() {return ok && (number>1);}
};

class sosuu_print {
	public:
		sosuu_print() {}
		void operator() (int x) {
			sosuu_hantei sh=x>1?std::for_each(
				slist+1,slist+x-1,sosuu_hantei(x)):sosuu_hantei(1);
			sh.get_result()&&printf("%d\n",x);
		}
};

int main(void) {
	std::generate(slist,slist+1000,suuti_gen);
	std::for_each(slist,slist+1000,sosuu_print());
	return 0;
}

[fulls]

お二人とも返信ありがとうございました。
>>みけCATさん
3通りもありがとうございます。
2つ目は...アセンブリ...
C/C++で書いた場合、":?"が入ってくるのは予想してましたが、これは...かなり予想外です。
私はアセンブリはさっぱりなのですが、結果はあっているようですね。
>>bitter_foxさん
率直な感想は「み、短い..」ですね。
ただ、Scalaもアセンブリ同様さっぱりです..
C/C++は短いものは短いですが、長いものは極端にコードが長くなるイメージがあります。

まだ少し募集を続けたいと思います。

[編集]bitter_foxさんの名前を直させていただきました。すいませんでした。

[h2so5]

外部ライブラリの使用が可能なら、いくらでも書き方はあります。

コード:

#include <ruby.h>
int main()
{
  ruby_init();
  rb_eval_string("p (2..1000).find_all{|n| (2..n-1).all?{|m| n % m != 0 }}");
  ruby_cleanup(0);
  return 0;
}

よく見たらifが入っていたので修正

[beatle]

>>beatleさん

(ﾟдﾟ)！僕は投稿してませんよ。

[fulls]

すいませんm(_ _)m
違う記事を見ててbeatleさんの名前がなぜか頭に残っていたもので..

[かずま]

エラトステネスの篩です。

コード:

#include <stdio.h>
#define N 1000
char b[N+1];
void g(int i, int j) { j <= N ? b[j] = 1, g(i, j + i) : 0; }
void f(int i) { i <= N ? !b[i] ? g(i, i), printf("%d\n", i) : 0, f(i + 1) : 0; }
int main(void) { f(2); return 0; }

[bitter_fox]

>>beatleさん
率直な感想は「み、短い..」ですね。
ただ、Scalaもアセンブリ同様さっぱりです..
C/C++は短いものは短いですが、長いものは極端にコードが長くなるイメージがあります。

bitter_foxです、よろしくお願いします。

Scalaのコードについて説明しておきますと、n to mというのはn.to(m)に相当し、toメソッドはnからmまで(m含む)の数列(Rangeクラスのインスタンス)を作ります。
countメソッドは引数に受け取った関数(この場合はIntの値を受け取りBooleanを返す関数)が真を返す個数を返します。

n % _ == 0がその関数になります。ここの_は一つ目の引数を表します。(以降_が出るたびに二つ目、三つ目となっていく)

オフトピック

細かい話をすれば、これはラムダ式をさらに簡素化した物で、m => n % m == 0と同じ働きをします。
Scalaのラムダ式は=>の前に引数リストが来て=>の後に本体が来ます。

filterは引数に受け取った関数(この場合もIntの値を受け取りBooleanを返す関数)が真を返す要素だけを残した数列を返します。
引数に渡しているisPrimeがその関数になります。

foreachは引数に受け取った関数(この場合はIntの値を受け取る関数)を全ての要素について実行します。

[fulls]

返信ありがとうございます。
h2so5さん
""内が数学の集合の要素を表すような感じなので何となく分かりました。
確かに外部のライブラリを使うと簡単ですね。
かずまさん
"エラトステネスの篩"は調べたらいろいろ出てきました。
こんな方法があったんですね。
ただ私は"?:"を使うのに慣れていないので、方法がわかっても自在に使いこなせなくて結局できなかった気がします。
bitter_foxさん
名前の件はすいませんでした。
プログラムの解説、ありがとうございます。
引数の取り方や演算子がCと似ているので、何とか判った...気になっただけですね...

結構プログラムを出していただいたのでこのトピックは解決とします。
皆さんありがとうございました。