Решето Эратосфена на Си

Постановка задачи.
Оформление решения на Си.
Курс молодого бойца по информатике (Язык Си).
cs.mipt.ru/c_intro

[@user-qy3jg1th1j]

Спасибо. Познавательно, но... Есть пара-тройка нюансов. Предисловие. Лет пять назад, когда занимался шифрованием на базе эллиптических кривых (EC Cryptography) тоже пытался найти алгоритмы поиска простых чисел. К сожалению, в наше время, требования к криптостойкости алгоритмов довольно высокие. Сейчас существуют специальные фермы, вычисляющие простые числа (очень большие, порядка 10^36, было лет пять назад). И для таких задач использование алгоритмов "Решето Эратосфена" и "Решето Эйлера" невозможно (очень большое выделение памяти для хранения массива). Что могу сказать. Во первых, сразу исключаются четные числа, кроме 2. Во вторых, 0, 1 и 2 - идут споры в математических кругах о том, являются ли эти числа простыми или нет (ну исключили, так исключили). В третьих, кроме числа 5, числа большие 5 и оканчивающиеся на 5 или 0 - не могут быть простыми. Что мы имеем в итоге. Для нахождения больших простых чисел, нужно проверять только числа заканчивающиеся на [1,3,7,9] (например, как остаток деления на 10), учитывая, числа 2 и 5 статически простыми. Далее - перебор делителей до квадратного корня из числа. Там тоже можно найти "усовершенствования", но по другому - никак. Если интересно, могу выложить код для CUDA (вычислять простые числа на CPU - считаю извращением ИМХО). А вот за технику "i * i < N" - СПАСИБО. Я вычислял на GPU квадратный корень (к сожалению на GPU и FPGA устройствах применение вызовов библиотечных функций (типа SQRT) невозможно по обьективным причинам. Но все равно лайк!

[@user-du7gn7xw7w]

Рекомендую собственный труд: "Закон расположения простых чисел найден". Надеюсь, оцените)))

[@lelelele1746]

добрый день! очень интересно посмотреть на код для CUDA, я только начинаю заниматься простыми числами, криптографией, почитал бы, что вы покажете или порекомендуете почитать

[@tark_wight]

@@lelelele1746 вы не один в ваших начинаниях. Хоть комментарию и 4 года, я хотел бы увидеть пример, о котором говорит автор.

[@tark_wight]

@@user-cl6nt2lz9z потому что интересна реализация. Потому что уже работал с CUDA и к параллельным вычислениям не горю желанием возвращаться. Банально есть чем заняться, чем интереса ради реализовывать велосипед.

[@user-no3rr2wk2g]

Простые числа - полезная штука. Взять тот же алгоритм шифрования RSA, где без них никак. Спасибо за видео!

[@Kirill2011l]

Огромное спасибо! Просто и понятно.

[@andrey6552]

Спасибо. Информативно и полезно :)

[@Mani_Fast]

спасибо огромное, все понятно

[@qadyrisrafilov7871]

А как можно из ряда чисел (без массива) найти самые большие три последовательно отсортировав по убыванию. На примере два самых больших. Желательно на {C}, о описанием можно. пожалуйста. Заранее спасибо за ответ #include #include int main() { int n,i; float max1,max2,max3,num; printf("Vvedite kolichestvo chisel "); scanf("%d", &n); for (i=1; inum) { max1=num; max2=max1; } else { max2=num; } } if (n==3) { if (num>max1) { max2=max1; max1=num; } else { if (num>max2) { max2=num; } } } } printf("First MAX=%.1f ", max1); printf("Second MAX=%.1f ", max2); return 0; }

[@user-zf8hu2bz1j]

При выводе стоит поставить нестрогое неравенство, иначе если крайнее число является простым, то оно не выведется

[@user-ee4hs4mb2z]

Ещё бы доску интерактивную вам!!!

[@sergowtf9873]

Тимофей, спасибо за доступное объяснение. Как вывести простые числа, например, от 30 до 100? Или из любого другого диапазона?

[@programer8]

так: #include #include #define N 100 int main() { bool isPrime; printf("Prime numbers: "); for (int i = 30; i < N; i++) { isPrime = true; for (int j = 2; j < i / 2; j++) if (i % j == 0) { isPrime = false; break; } if (isPrime) printf("%3d", i); } return 0; }

[@den3v]

Если бы было рассказано о применениях то было бы еще интереснее

[@one_another_goal]

домашка доступна только физтехам?

[@vyacheslavsmyshlyaev188]

Тимофей, интересны временные оценки. Сколько времени тратит программа для поиска простых чисел скажем в 5 000 000 массиве? У меня есть своя реализация, совершенно иная. Интересно сравнить, можно где-то скачать Ваш код?

[@user-xy5vb1mn7m]

#include #define N 25 int main(int argc, char* argv[]) { int sieve[N] = {0}; for(int i = 2; i*i < N; ++i) if (sieve[i] == 0) for(int k = i*i; k < N; k += i) sieve[k] = 1; for(int i = 0; i < N; ++i) printf("%3d", i); printf(" "); for(int i = 0; i < N; ++i) printf("%3d", sieve[i]); printf(" "); printf("Prime numbers: "); for(int i = 2; i < N; ++i) if (sieve[i] == 0) printf("%3d", i); printf(" "); return 0; }

[@user-tg5jj8iw6p]

у меня чуть по другому первый цикл. Результат: Всего в диапазоне [0, 5000000] 348513 простых чисел Время заполнения массива: 0.019 сек (~ 0 мин) Время вычисления: 0.152 сек (~ 0 мин) Время записи данных в файл: 1.463 сек (~ 0 мин) Общее время выполнения: 1.634 сек (~ 0 мин)

[@user-tg5jj8iw6p]

но его реализация мне больше нравится.

[@jalolturdiev9727]

Thank you

[@arinaterenteva8120]

подскажите пожалуйста: использую dev c ++, написала эту программку, но компилятор в строке " простые числа " выводит только 2 и 3. Копировала ваш код, все точно так же. Может знаете, в чем проблема?

[@petrpetr9576]

код скиньте

[@user-ll9ue9zl6m]

такая же проблема, как исправить?

[@logius84]

очень хорошо объясняешь, но.... где это все можно использовать? Хотелось бы увидеть примеры использования

[@gkritsv]

Тимофей Хирьянов - красавчик! Давайте веб разбирать ORM, Flask - чтобы алгоритмы в интерфейс выводить.

[@Ca1vema]

На самом деле не особо понятно. На доске преподаватель рассказывал про деление и кратность числа, а в коде ничего из этого нет. Понимаю, "школьная математика и сейчас это не цель", но не понимаю почему сначала говорится об одном, а делается по-другому.

[@alexeyvolk5293]

Ну, кратность сама по себе не используется. Просто все числа, кратные простому n, можно отсеять, пройдя по массиву (решету) начиная с элемента под индексом n, с шагом n

[@user-ib8rv1vr4r]

Так. А теперь привет умникам: как доказать, что мы имеем право идти вторым циклом от i^2. Помогите, а то я видел такую реализацию и автору спасибо, но это ведь только наблюдения на конкретном примере. Кто-то докажет строго?

[@danilbutygin238]

крутые у тебя видио по физре

[@user-ib8rv1vr4r]

@@danilbutygin238 Это домашка. На удаленке сдаем это.)))

[@danilbutygin238]

@@user-ib8rv1vr4r я догадался

[@user-ib8rv1vr4r]

Ну на самом деле ничего сложного: ну, например, на очереди у нас число і=p. Но мы ведь уже "вычеркнули" все числа вида 2*k, 3*k, 5*k, ... и стоит начинать именно с p*p, так как все простые числа, меньше текущего числа, уже были и нет смысла их проверять. Не сильно строго, но для программистов - самое оно.)

[@igorustenko2503]

Все что понял, что алгоритм написан верно. Но объяснения автора, что из чего вытекает в расчетах и почему - сумбур (все само собой получается, и все хорошо, не разбирайтесь, просто запоминайте). Возьмите либо пример алгебраически проще, либо уж объясняйте детальнее.

[@criterrors]

Хороший пример того, когда индексы массива являются конечными значениями, а значения массива - мусором😁

[@emilialove.7282]

Кто в каком классе? Я в 5

[@Mani_Fast]

11