0

「 n番目の素数を計算する」ための最短のCコードは何ですか?

意味のある文字の点で最短。つまり、セミコロン、空白以外の文字、キーワード、カンマの数。

入力：

改行で区切られた、標準入力からの整数n 。入力は EOF で終了します。

出力：

入力nの直後に、n番目の素数を改行で区切って標準出力に出力します。

(素数は < 10,000、つまりn < 1,230 であると想定できます。)

テストケース:

Input:
    1
    2
    4
    8
    32
    999
    42
    5

Output:
    2
    3
    7
    19
    131
    7907
    181
    11

私の試み：

 #define m 10000
 a[m],b[m],x;

 main(i,j){
   for(i=2;i<m;i++)
      {
       if (!a[i])
       for (b[++x]=i,j=2*i;j<m;j+=i)
            a[j]=1;
      }
   for(;~scanf("%d",&i);printf("%d\n",b[i]));
  }

この問題では、可読性は問題ではありません。時間とメモリの点でコストがかかるが、制約を満たすコードは、ここではより良いと見なされます。

4

3 に答える 3

7

Mathematica: 13文字

Prime@Input[]

Prime機能が組み込まれています。

REPL として: 34文字

While[0<(s=Input[]),Print@Prime@s]

または、29文字でちょうど 10,000 回実行します。

Print@Prime@Input[]~Do~{1*^4}
于 2010-02-14T10:12:41.843 に答える
3

C：104文字

i,t,n;g(){!--n?t=1:g();for(i=++t;1<--i;i=t%i?i:t++);}main(){for(;~scanf("%d",&n);g(),printf("%d\n",t));}

（そしてもちろん、それは指数関数的な時間で実行されます。）

（ところで、Cに制限するのは退屈です。最近のほとんどcode-golfはここにありlanguage-agnosticます。）

于 2010-02-14T16:27:15.693 に答える
2

これがPythonでの試みです。入力形式で何を意味するのか正確にはわかりませんでしたが、これですべてのケースに対応できるはずです。また、それはひどく遅く、入力を処理する準備ができる前に素数を生成するのに数秒かかります。奇妙な入力解析により、出力の生成を開始する前にすべての入力が一度に丸呑みされるため、数値を入力してリストをEOFで終了し、一度に回答を取得する（またはファイルから入力をリダイレクトする）必要があります。

import sys
p=[2]
for i in xrange(3,105000,2):
    if all(i%x for x in p):
        p.append(i)
print '\n'.join(str(p[int(i)-1]) for i in sys.stdin.read().split())

152文字（スペース付き）

130文字（スペースなし）

于 2010-02-14T09:10:13.283 に答える