Спасибо. Познавательно, но... Есть пара-тройка нюансов. Предисловие. Лет пять назад, когда занимался шифрованием на базе эллиптических кривых (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) невозможно по обьективным причинам. Но все равно лайк!
добрый день! очень интересно посмотреть на код для CUDA, я только начинаю заниматься простыми числами, криптографией, почитал бы, что вы покажете или порекомендуете почитать
@@user-cl6nt2lz9z потому что интересна реализация. Потому что уже работал с CUDA и к параллельным вычислениям не горю желанием возвращаться. Банально есть чем заняться, чем интереса ради реализовывать велосипед.
А как можно из ряда чисел (без массива) найти самые большие три последовательно отсортировав по убыванию. На примере два самых больших. Желательно на {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; }
Тимофей, интересны временные оценки. Сколько времени тратит программа для поиска простых чисел скажем в 5 000 000 массиве? У меня есть своя реализация, совершенно иная. Интересно сравнить, можно где-то скачать Ваш код?
у меня чуть по другому первый цикл. Результат: Всего в диапазоне [0, 5000000] 348513 простых чисел Время заполнения массива: 0.019 сек (~ 0 мин) Время вычисления: 0.152 сек (~ 0 мин) Время записи данных в файл: 1.463 сек (~ 0 мин) Общее время выполнения: 1.634 сек (~ 0 мин)
подскажите пожалуйста: использую dev c ++, написала эту программку, но компилятор в строке " простые числа " выводит только 2 и 3. Копировала ваш код, все точно так же. Может знаете, в чем проблема?
На самом деле не особо понятно. На доске преподаватель рассказывал про деление и кратность числа, а в коде ничего из этого нет. Понимаю, "школьная математика и сейчас это не цель", но не понимаю почему сначала говорится об одном, а делается по-другому.
Ну, кратность сама по себе не используется. Просто все числа, кратные простому n, можно отсеять, пройдя по массиву (решету) начиная с элемента под индексом n, с шагом n
Так. А теперь привет умникам: как доказать, что мы имеем право идти вторым циклом от i^2. Помогите, а то я видел такую реализацию и автору спасибо, но это ведь только наблюдения на конкретном примере. Кто-то докажет строго?
Ну на самом деле ничего сложного: ну, например, на очереди у нас число і=p. Но мы ведь уже "вычеркнули" все числа вида 2*k, 3*k, 5*k, ... и стоит начинать именно с p*p, так как все простые числа, меньше текущего числа, уже были и нет смысла их проверять. Не сильно строго, но для программистов - самое оно.)
Все что понял, что алгоритм написан верно. Но объяснения автора, что из чего вытекает в расчетах и почему - сумбур (все само собой получается, и все хорошо, не разбирайтесь, просто запоминайте). Возьмите либо пример алгебраически проще, либо уж объясняйте детальнее.
Спасибо. Познавательно, но... Есть пара-тройка нюансов. Предисловие. Лет пять назад, когда занимался шифрованием на базе эллиптических кривых (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) невозможно по обьективным причинам. Но все равно лайк!
Рекомендую собственный труд: "Закон расположения простых чисел найден". Надеюсь, оцените)))
добрый день! очень интересно посмотреть на код для CUDA, я только начинаю заниматься простыми числами, криптографией, почитал бы, что вы покажете или порекомендуете почитать
@@lelelele1746 вы не один в ваших начинаниях. Хоть комментарию и 4 года, я хотел бы увидеть пример, о котором говорит автор.
@@user-cl6nt2lz9z потому что интересна реализация. Потому что уже работал с CUDA и к параллельным вычислениям не горю желанием возвращаться. Банально есть чем заняться, чем интереса ради реализовывать велосипед.
Простые числа - полезная штука. Взять тот же алгоритм шифрования RSA, где без них никак. Спасибо за видео!
Огромное спасибо! Просто и понятно.
Спасибо. Информативно и полезно :)
спасибо огромное, все понятно
Тимофей, спасибо за доступное объяснение. Как вывести простые числа, например, от 30 до 100? Или из любого другого диапазона?
так:
#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;
}
Thank you
А как можно из ряда чисел (без массива) найти самые большие три последовательно отсортировав по убыванию. На примере два самых больших. Желательно на {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;
}
Ещё бы доску интерактивную вам!!!
При выводе стоит поставить нестрогое неравенство, иначе если крайнее число является простым, то оно не выведется
Тимофей, интересны временные оценки. Сколько времени тратит программа для поиска простых чисел скажем в 5 000 000 массиве? У меня есть своя реализация, совершенно иная. Интересно сравнить, можно где-то скачать Ваш код?
#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;
}
у меня чуть по другому первый цикл. Результат:
Всего в диапазоне [0, 5000000] 348513 простых чисел
Время заполнения массива: 0.019 сек (~ 0 мин)
Время вычисления: 0.152 сек (~ 0 мин)
Время записи данных в файл: 1.463 сек (~ 0 мин)
Общее время выполнения: 1.634 сек (~ 0 мин)
но его реализация мне больше нравится.
домашка доступна только физтехам?
Если бы было рассказано о применениях то было бы еще интереснее
подскажите пожалуйста:
использую dev c ++, написала эту программку, но компилятор в строке " простые числа " выводит только 2 и 3. Копировала ваш код, все точно так же. Может знаете, в чем проблема?
код скиньте
такая же проблема, как исправить?
очень хорошо объясняешь, но.... где это все можно использовать? Хотелось бы увидеть примеры использования
Тимофей Хирьянов - красавчик! Давайте веб разбирать ORM, Flask - чтобы алгоритмы в интерфейс выводить.
На самом деле не особо понятно.
На доске преподаватель рассказывал про деление и кратность числа, а в коде ничего из этого нет.
Понимаю, "школьная математика и сейчас это не цель", но не понимаю почему сначала говорится об одном, а делается по-другому.
Ну, кратность сама по себе не используется. Просто все числа, кратные простому n, можно отсеять, пройдя по массиву (решету) начиная с элемента под индексом n, с шагом n
Так. А теперь привет умникам: как доказать, что мы имеем право идти вторым циклом от i^2. Помогите, а то я видел такую реализацию и автору спасибо, но это ведь только наблюдения на конкретном примере. Кто-то докажет строго?
крутые у тебя видио по физре
@@danilbutygin238 Это домашка. На удаленке сдаем это.)))
@@user-ib8rv1vr4r я догадался
Ну на самом деле ничего сложного: ну, например, на очереди у нас число і=p. Но мы ведь уже "вычеркнули" все числа вида 2*k, 3*k, 5*k, ... и стоит начинать именно с p*p, так как все простые числа, меньше текущего числа, уже были и нет смысла их проверять. Не сильно строго, но для программистов - самое оно.)
Все что понял, что алгоритм написан верно. Но объяснения автора, что из чего вытекает в расчетах и почему - сумбур (все само собой получается, и все хорошо, не разбирайтесь, просто запоминайте). Возьмите либо пример алгебраически проще, либо уж объясняйте детальнее.
Хороший пример того, когда индексы массива являются конечными значениями, а значения массива - мусором😁
Кто в каком классе? Я в 5
11