Все простые числа от 0 до 1000

9

Можно ли сделать этот код C меньше? Распечатывает все простые числа от 0 до 1000.

С, 89 символов

int i,p,c;for(i=2;i<1e3;i++){c=0;for(p=2;p<i;p++)if(i%p==0)c++;if(c==0)printf("%u\n",i);}
Йонас Грунау
источник
6
Просто для того, чтобы предупредить некоторые «Мы не хотим проблем, связанных с языком», просьба о помощи в разработке кода - это тема и другая история, чем проблемы.
Мартин Эндер
4
Нужно ли сохранять алгоритм или только конечный результат?
Джон Дворак
Я бы начал с 2, чтобы быть строго точным, так как это печатает 0 и 1.
Гистократ
Вы пытаетесь заставить код выполняться быстрее или используете меньше символов в исходном коде?
user3629249
1
Поскольку вы просите о помощи в гольфе, было бы полезно включить в ваш пост количество персонажей вашего текущего решения (я делаю его как 89).
Марк Рид

Ответы:

7

59 57 байт

На основе решения @feersum, но проверка первичности может быть продолжена

for(int p=1,d;d=p++%999;d||printf("%d\n",p))for(;p%d--;);

Отредактировано на основе комментариев Runer112

Alchymist
источник
2
Связанная проверка может быть golfed немного больше: d=p++%999. В остальном это выглядит довольно герметично для игры в гольф!
Runer112
10

67 байт

В Си нет реальной альтернативы пробному делению, но это, безусловно, можно немного поиграть в гольф.

for(int p=1,d;p++<999;d&&printf("%d\n",p))for(d=p;--d>1;)d=p%d?d:1;

Требуется начальное объявление C99, что экономит 1 байт.

feersum
источник
6

(Я написал это, не осознавая ограничений на размер целых чисел в C, так что, скорее всего, это не очень полезно для сокращения кода.)

Сначала пару слов об алгоритме. Перед тем, как сыграть в свой код, вы должны подумать о наилучшей общей стратегии, чтобы получить результат.

Вы проверка простоты, выполнив пробное деление - тестирование каждый потенциальный делителя pиз i. Это дорого в символах, потому что это занимает два цикла. Таким образом, тестирование простоты без цикла может спасти символы.

Часто более короткий подход заключается в использовании теоремы Вильсона : число nявляется простым тогда и только тогда, когда

fact(n-1)%n == n-1

где fact- факториальная функция Поскольку вы тестируете все возможное nот и 1до 1000, легко избежать внедрения факториала, отслеживая работающий продукт Pи обновляя его P*=nпосле каждого цикла. Вот реализация этой стратегии на Python для печати простых чисел до миллиона.

С другой стороны, тот факт, что ваша программа должна быть только до 1000, открывает другую стратегию: тест первичности Ферма . Для некоторых aкаждое простое число nудовлетворяет

pow(a,n-1)%n == 1

К сожалению, некоторые композиты nтакже проходят этот тест для некоторых a. Это псевдопричины Ферма . Но a=2и a=3не терпите неудачу вместе до тех пор n=1105, пока их не будет достаточно для проверки простых чисел до 1000. (Если бы вместо 1000 использовалось 100, вы могли бы использовать только a=2.) Итак, мы проверяем простоту с помощью (кода без ключа)

pow(2,n-1)%n == 1 and pow(3,n-1)%n == 1

Это также не может распознать простые числа 2 и 3, поэтому они должны быть в специальном случае.

Эти подходы короче? Я не знаю, потому что я не пишу код на C. Но это идеи, которые вы должны попробовать, прежде чем остановиться на куске кода, чтобы начать набирать символы.

XNOR
источник
1
Теорема Уилсона бесполезна в C, потому что ints 32-битные. То же самое касается Ферма.
feersum
@feersum Ох, стреляй. Это проблема и для факториалов. Есть ли тип big-int?
xnor
@xnor Не встроенный.
Мартин Эндер
1
если он определен, fact(int n, int m) { return (n==0) ? 1 : (n*f(n-1)) % m; }то результат не будет переполнен 32-битным целым числом даже для довольно больших значений n. ( mэто модуль)
apnorton
@anorton Я думаю, ты имеешь в виду (n*fact(n-1,m)) % m. Что подчеркивает проблему: вы не можете избежать рекурсии в реализации, factпотому что mона будет отличаться для каждой итерации внешнего цикла.
HVd
4

78 77 символов

(Просто применил некоторые трюки, изученные на других языках.)

int i=0,p,c;for(;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}

76 символов в режиме C99

for(int i=0,p,c;i<1e3;i++){c=0;for(p=2;p<i;)c+=i%p++<1;c||printf("%u\n",i);}
manatwork
источник
2

58 символов (или 61 для полной программы)

Еще одно повторное использование моего ответа на аналогичный вопрос .
РЕДАКТИРОВАТЬ : автономный кусок кода, нет функции для вызова.

for(int m,n=2;n<999;m>1?m=n%m--?m:n++:printf("%d\n",m=n));

Полная программа:

n=2;main(m){n<999&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}
ugoren
источник
1

67 64 байта

Вдохновленный решением Алхимика:

int i=1,p;for(;i++<1e3;p-i||printf("%d\n",i)){p=1;while(i%++p);}
Сахиль Арора
источник