Какой самый короткий способ вычислить n-е простое число? - PullRequest
0 голосов
/ 14 февраля 2010

Какой самый короткий код C до " Вычислить n -ое простое число "?

Наименьшее число значимых символов , т. Е. количество точек с запятой, непробельных символов, ключевых слов и запятых .

Введите:

Целые числа n от стандартного ввода, разделенные новыми строками. Ввод будет завершен EOF.

Выход:

Сразу после ввода n выведите n -ое простое число на стандартный вывод, разделенный новыми строками.

(Вы можете считать, что простые числа <10 000, т. Е. <em>n <1230.) </p>


Контрольные примеры:

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]));
  }

Для этой проблемы удобочитаемость не является проблемой. Более дорогой код с точки зрения времени и памяти, но удовлетворяющий ограничению, будет рассматриваться здесь лучше.

Ответы [ 3 ]

7 голосов
/ 14 февраля 2010

Mathematica: 13 символов

Prime@Input[]

Встроенная функция Prime.


В качестве ответа: 34 символов

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

или, выполнив ровно 10000 раз, 29 символов:

Print@Prime@Input[]~Do~{1*^4}
4 голосов
/ 14 февраля 2010

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.)

2 голосов
/ 14 февраля 2010

Вот попытка в 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 символов (без пробелов)

...