Ваша задача, если вы решите принять ее, - написать программу / функцию, которая принимает целое число N в качестве входных данных. Программа / функция должна вывести / вернуть список первых N простых чисел. Но здесь есть одна загвоздка: вам не разрешено использовать простые символы в вашем коде. Простым символом является символ, чья кодовая точка Unicode является простым числом. В диапазоне ASCII для печати это:

%)+/5;=CGIOSYaegkmq

Но правило также применяется к не-ASCII символам, если ваш код использует их.

• Допустимым входным значением является целое число N, где 0 <N <= T , где вы можете выбрать T , но оно должно быть больше или равно 10000. T не обязательно должно быть конечным.
• Для недопустимых входных данных (нецелые числа, целые числа вне диапазона) выведите исключение или не выводите / не возвращайте ничего / ноль.
• Целое число с начальным / конечным пробелом в качестве входных данных считается недействительным.
• Целое число со +знаком в качестве входного признака считается недействительным.
• Целое число с ведущими нулями в качестве входных данных считается допустимым.
• Если ваш язык позволяет вам передавать уже проанализированное целое число в качестве входных данных, вышеприведенные правила синтаксического анализа (кроме диапазона) не применяются, потому что int уже проанализирован.
• Ввод всегда базовый-10.
• Использование встроенных простых генераторов и тестеров простоты (включая функции факторизации простых чисел) не допускается.
• Исходное ограничение накладывается на символы Юникода, но подсчет байтов для оценки может быть в другой кодировке, если хотите.
• Вывод может содержать один завершающий перевод строки, но это не обязательно.
• Если вы выводите / возвращаете список простых чисел в виде строки, то каждое простое число должно быть разделено одним или несколькими нецифровыми символами. Вы можете выбрать, какой разделитель вы используете.
• Это задача кода-гольфа , выигрывает самый короткий код в байтах.

Фрагмент стека для проверки вашего кода

Вы можете использовать приведенный ниже фрагмент стека, чтобы убедиться, что ваш код не содержит простых символов:

var primes=[],max=10000;for(var i=2;i<=max;i++){primes.push(i);}for(var N=2;N<Math.sqrt(max);N++){if(primes.indexOf(N)===-1){continue;}primes=primes.filter(function (x){return x===N||x%N!==0;});}function setText(elem,text){var z=('innerText' in elem)? 'innerText' : 'textContent';elem[z]=text;}function verify(inputCode,resultSpan){var invalidChars=[];var success=true;for(var i=0;i<inputCode.length;i++){var cc = inputCode.charCodeAt(i);if (cc>max){setText(resultSpan,"Uh oh! The char code was bigger than the max. prime number calculated by the snippet.");success = false;break;}if (primes.indexOf(cc)!==-1){invalidChars.push(inputCode[i]);}}if (invalidChars.length===0&&success){setText(resultSpan, "Valid code!");}else if(success) {  var uniqueInvalidChars = invalidChars.filter(function (x, i, self){return self.indexOf(x)===i;});setText(resultSpan, "Invalid code! Invalid chars: " + uniqueInvalidChars.join(""));    }}document.getElementById("verifyBtn").onclick=function(e){e=e||window.event;e.preventDefault();var code=document.getElementById("codeTxt").value;verify(code,document.getElementById("result"));};

Enter your code snippet here:<br /><textarea id="codeTxt" rows="5" cols="70"></textarea><br /><button id="verifyBtn">Verify</button><br /><span id="result"></span>

CJam, 19 18 30 34 33 19 17 21 20 байт

Попробуйте онлайн.

{_3\#,2>__ff*:~-<N*}

Это, наверное, один из самых ужасно неэффективных алгоритмов, которые я когда-либо реализовывал. Но я сделал это для размера!

Мой ответ состоит из блока кода, который действует как анонимная функция в CJam. Запустите его с целым числом, непосредственно предшествующим ему в стеке, и полученный список будет выгружен в стек. Я рассматриваю верхнюю границу ввода как бесконечную, поэтому мне не нужно проверять эту границу.

Мой алгоритм начинается с повышения 3 до степени inputth, которая гарантированно даст число, большее, чем input-ое простое число, если введенные данные верны. Затем генерируется список целых чисел от 2 до этого числа минус один, что является достаточно большим диапазоном для размещения всех простых чисел, которые мы хотим. Чтобы избавиться от составных чисел ... вздох ... мы создаем список каждого попарного продукта, который должен генерировать все составные числа от 4 до некоторого тупо большого значения, достаточно большого для наших целей. Затем нужно просто удалить каждый элемент из исходного списка, который находится в этом составном списке, обрезать его до первых inputэлементов и соединить элементы с символом новой строки.

Алгоритм должен работать для любого входа. Однако, достаточно ли у переводчика / компьютера памяти или времени - это совсем другой вопрос, потому что требования к времени и пространству экспоненциальны относительно ввода. Таким образом, если входное значение больше, чем около 5 для онлайн-переводчика или около 8 для автономного переводчика, то ответ на этот вопрос, вероятно, нет.

Джава. 474 байта

i\u006dport j\u0061v\u0061.util.*\u003bvoid b(int b\u0029{Lon\u0067 c\u003d2L,d,f[]\u003d{}\u003bfor(f\u003dArr\u0061ys.copy\u004ff(f,b\u0029,Arr\u0061ys.fill(f,0L\u0029\u003bb-->0\u003b\u0029for(d\u003d0L\u003bf[b]<1\u003bf[b]\u003dd<1?c:f[b],d\u003d0L,c\u002b\u002b\u0029for(lon\u0067 h:f\u0029d\u003dh>0&&c\u002fh*h\u003d\u003dc?1:d\u003bj\u0061v\u0061x.x\u006dl.bind.JAXB.un\u006d\u0061rsh\u0061l(""\u002bArr\u0061ys.\u0061sList(f\u0029,Lon\u0067.cl\u0061ss\u0029\u003b}

Принимает ввод через аргумент функции, выводит через выброшенное исключение.

Отступ:

i\u006dport j\u0061v\u0061.util.*\u003b
void b(int b\u0029{
    Lon\u0067 c\u003d2L,d,f[]\u003d{}\u003b
    for(f\u003dArr\u0061ys.copy\u004ff(f,b\u0029,Arr\u0061ys.fill(f,0L\u0029\u003bb-->0\u003b\u0029
        for(d\u003d0L\u003bf[b]<1\u003bf[b]\u003dd<1?c:f[b],d\u003d0L,c\u002b\u002b\u0029
            for(lon\u0067 h:f\u0029
                d\u003dh>0&&c\u002fh*h\u003d\u003dc?1:d\u003b
    j\u0061v\u0061x.x\u006dl.bind.JAXB.un\u006d\u0061rsh\u0061l(""\u002bArr\u0061ys.\u0061sList(f\u0029,Lon\u0067.cl\u0061ss\u0029\u003b
}

Удаленные символы удалены:

import java.util.*;
void b(int b){
    Long c=2L,d,f[]={};
    for(f=Arrays.copyOf(f,b),Arrays.fill(f,0L);b-->0;)
        for(d=0L;f[b]<1;f[b]=d<1?c:0,d=0L,c++)
            for(long h:f)
                d=h>0&&c/h*h==c?1:d;
    javax.xml.bind.JAXB.unmarshal(""+Arrays.asList(f),Long.class);
}

Объяснение:

Long c,d,f[]={};                                                //Initialize variables.

for(f=java.util.Arrays.copyOf(f,b),Arrays.fill(f,0L);b-->0;)
    f=java.util.Arrays.copyOf(f,b),Arrays.fill(f,0L)            //Initialize f to an array of 0's.
                                                     b-->0      //Iterate over the first b primes.

for(d=0L;f[b]<1;f[b]=d<1?c:0,d=0L,c++)
    d=0L                        d=0L                            //Initialize d to 0.
         f[b]<1                      c++                        //Increment c while the b'th prime is 0.
                f[b]=d<1?c:0                                    //If d = 0, the b'th prime = c, else continue.

for(long h:f)                                                   //Iterate over all found primes.

d=h>0&&c/h*h==c?1:d;
  h>0                                                           //Ignore non-found primes.
       c/h*h==c                                                 //Equivalent to c%h==0
               ?1:d                                             //If h is prime and c is divisible by h, d = 1. Otherwise d stays unchanged.

javax.xml.bind.JAXB.unmarshal(""+Arrays.asList(f),Long.class)   //Print solution to stderr
javax.xml.bind.JAXB.unmarshal(                   ,Long.class)   //Prints what's contained to stderr.
                                 Arrays.asList(f)               //Convert f to list.
                              ""+                               //Convert to string.

Мое оригинальное решение использовало returnутверждение. Задав этот вопрос на StackOverflow, regettman был достаточно любезен , чтобы обеспечить способ для вывода / возврат без использования простых писем.

Как обычно, предложения приветствуются :)

Руби, 74

->n,*o{o<<[2..n*n][0].find{|x|!o.find{|y|1.>x.^y.*x.div y}}until o[n-1]
o}

Объяснение:

*oинициализирует пустой выходной массив. пока у него нет nэлементов, мы найдем наименьшее число> = 2, которое не делит ни один элемент в данный момент o, и добавим его к o. Чтобы проверить на деление, yikes. Все хорошие операторы запрещены, и я даже не могу использовать divmod. Лучшее, что я мог видеть, - это использовать x.div y, где x делится на y и округляется, а затем умножается на y. Если он равен x, округления не было, поэтому y делит x. 1.>x.^является тестом на равенство, проверяющим, равен ли xor результат 0. Оператор .before before заключается в том, что нельзя смешивать .вызовы -free-операторов и вызовы методов без скобок.

Изменить: спецификации проверки диапазона были добавлены после того, как я опубликовал это, я думаю. Для соответствия требуется 79 символов:

->n,*o{o<<[*2..-~n*n].find{|x|!o.find{|y|1.>x.^y.*x.div y}}until o[n-1]||n<1
o}

CJam, 38 37 30 байт

{_~2#,2>\{(\{1$37c~},\p}*'<(~}

Попробуй здесь

Я думаю, что это должно соответствовать всем правилам и работает для любого неотрицательного N (т. Е. T бесконечно). Это ужасно неэффективно, так что не пробуйте это для больших количеств.

Это блок, наиболее близкий к (неназванной) функции, который ожидает целое число в стеке, печатает все простые числа и покидает стек без ввода. Для всех неверных входных данных он либо выдаст ошибку, либо ничего не выведет.

Большая часть кода является проверкой ввода, за которой следует сито Эратосфена. Мне нужно было только обойти ограничение ввода в 3 местах:

• )это инкремент в CJam. Мне это нужно было один раз, но я мог заменить его на ~(побитовое дополнение), потому что в любом случае я возводил в квадрат числа.
• %по модулю Я использую 37c~вместо этого, который сначала создает персонажа, %а затем Эвал. Это делает код намного медленнее.
• ;выскакивает и сбрасывает элемент из стека. Мне нужно сделать это в конце. Вместо этого я использую, '<(~который толкает персонажа <, уменьшает его, а eval это.

Bash + coreutils, 227 байт

printf -vb br`dc<<<Di14B8209P`
printf -vc -- $[$1-0]
[ "${1#$c}" -o $c -lt 1 ]||{
for i in {2..104729}
{
for f in `jot $[i-1] $[i-1] 1`
{
[ 0 -lt `dc<<<"$i $f~p"` ]||$b
}
[ $f -lt 2 ]&&printf $i\ &&: $[c--]
[ $c -lt 1 ]&&$b
}
}

Это было довольно сложно. Некоторые вещи, с которыми я столкнулся:

• Большинство циклов ( whileи until) непригодны для использования, потому что они наиболее близки doneк ключевым словам оболочки и не могут быть результатом раскрытия переменной (если evalне используется, но это тоже не так). Единственный используемый цикл - это for/, inкоторый позволяет {/ }вместо do/ done. for (( ; ; ))также не пригоден для использования.
• =отсутствует, поэтому нам нужен другой способ присвоения переменных. printf -vхорошо для этого.
• Мы знаем, что p (10000) равно 104729, поэтому для внешнего цикла для потенциальных простых чисел мы можем просто выполнить цикл от 2 до 104729 и прервать его, как только у нас будет достаточно простых чисел.
• jotгенерирует список потенциальных факторов во внутреннем цикле. Если потенциальный фактор делит потенциальное простое число, то оно не простое, и мы вырываемся рано
• К счастью break, это встроенная оболочка, а не ключевое слово, поэтому может быть сгенерировано в результате расширения. dcпреобразует базовый номер 13 в поток байтовeak .
• Чтобы проверить, делит ли потенциальный фактор потенциальное простое число, мы не можем использовать обычные /или %арифметические операторы оболочки. Так что это передается оператору dcs ~, который помещает частное и остаток в стек.
• -lt - less-than - единственный используемый оператор сравнения оболочек.
• echoбесполезно для вывода. printfработает, пока мы избегаем%

Правильно получить подтверждение ввода - это немного больно. Это ничего не возвращает в случае неверного ввода.

Выход:

$ ./primenoprime.sh 10
2 3 5 7 11 13 17 19 23 29 $ 

Haskell, 90 байт

\n->[fst c|c<-zip[p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]][1..n]]

Это анонимная функция, которая принимает целое число в nкачестве входных данных.

Как это работает: [p|p<-[2..],not$or[b>p-1&&b-1<p|b<-[u*v|u<-[2..p-1],v<-[2..p-1]]]](первый пример однострочных простых чисел в вики Haskell, но с elemзамененной функцией) создает бесконечный список простых чисел. zipона с числами от 1до , nчтобы сделать список (prime, seq. number)пар. Удалить последовательность номер, опять же. Результатом является список простых чисел длиныn .

Ржавчина, 64897 байт

|n|println!{"{:?}",&[2,3,6-1,7,11,13,17,19,23,29,31,37,41,43,47,60-7,0x3b,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,0x97,0x9d,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,0xfb,0x101 ...}

(код пропущен из-за ограничения символов, полное решение здесь )

Следующие свойства ржавчины становятся недоступными из-за основного ограничения:

• вызовы функций, так как они требуют ')'
• регулярные привязки, так как они требуют let (e)
• макроопределения, они требуют макро-правил! (А, е, м)
• операторы соответствия, они требуют соответствия (a, m) и => (=)
• изменчивость, поскольку она всегда вводится с ключевым словом mut (m).
• возврат (е), перерыв (а, е), продолжение (е)
• еще (е)

Что вы можете технически использовать:

• если. Но без них они бесполезны в контексте выражения, поэтому хороши только для побочных эффектов.
• макросы. Стандартные макросы, такие как print! обычно сопровождаются (), но на самом деле вместо них допустимо использовать {} или []. Без этого задача была бы невозможна.
• замыкания, в самом узком смысле. Вы не можете вызывать их (require ()) или связывать их (требует let), но вы можете определить один нерекурсивный. Без этого задача, очевидно, стала бы невозможной.
• Структуры.
• для петель. Они многообещающие, так как на самом деле допускают привязку переменных и используют итератор, который все еще можно определить с помощью синтаксиса диапазона. Итератор может даже быть выражением.
• Встроенные операторы, кроме +,% и /. Короткозамкнутые логические операторы кажутся многообещающими.

Я просто не мог сделать что-нибудь в комплекте с этими инструментами. Мне жаль. Осталось только включить первые 10000 простых чисел, очищенных от 5. По крайней мере, вы можете нарезать его и найти правильное решение в самом узком смысле этого слова.

Мне бы очень хотелось, чтобы эксперты по дайвингу на Тарюнге (или на Rust!) Сказали мне, могу ли я сделать что-то лучше!

GNU APL, 75 68 67 65 59 56 55 символов

⎕IOдолжно быть 1.

∇z←p n
z←2,j←3
j←j--2
→2×⍳∨⌿1>z|j
z←z,j
→2×⍳n>⍴z
z←n↑z∇

Я вернулся спустя несколько месяцев, осознав, что у меня есть дополнительное место!

Pyth - 12 байт

Использует основную функцию факторизации Пита, чтобы увидеть, является ли # простым. Использование !tPTтрюк предложил мне в моем ответе для простых чисел под миллион проблем.

<f!tPTr2^T6Q

Поскольку фильтр работает только для простых чисел под n, а не для первых n, я просто посмотрел обратное число pi (x) для 10000 и получил 104000, поэтому я использую простые числа меньше 10 и получаю первые n. Это на самом деле не работает, поэтому вы должны проверить, заменив ^T6на ^T3и ограничив n до 1000. Ввод из stdin и вывод в stdout.

<          Q     Slice first n
f     r2^T6      filter on range 2->10⁶
 !               Logical not (gives true if tail is empty)
  t              Tail (all but first, so gives empty if prime fact is len 1)
   PT            Prime factorization of filter var (len 1 if num is prime)