Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Фоновая коррекция изображения http://www.cyberforum.ru/cpp-beginners/thread660353.html
Мне надо написать прогу, которая корректировала бы фон изображения по алгоритму:Для каждого пикселя изображения 3 (результат) : (R3,G3,B3)=(R2-R1,G2-G1,B2-B1)+Del, где Del это значение scrollbar от...
C++ выполните расчет стоимости, использованного интернет-трафика
помогите пожалуйста, написать программу в visual c++: Выполните расчет стоимости, использованного интернет-трафика, если в ночные часы предоставляется скидка в 20%. (стоимость мегабайта и время...
Элементарный математический код, но почему то всегда равно 0,0000 C++
Элементарный математический код, но почему то всегда равно 0,0000. Тут я еще использую старые функции ввода-вывода, потому что так надо на лабораторную. Вот код: #include<iostream>...
C++ Нахождение суммы ряда с заданной точностью Помогите решить задачу что то не как не могу определить с чего начать. http://www.cyberforum.ru/cpp-beginners/thread660307.html
C++ Количество точек с целочисленными координатами внутри (не включая границ) произвольного многоугольника http://www.cyberforum.ru/cpp-beginners/thread660306.html
Есть вот такая задача. Координаты вершин подаются в порядке обхода по часовой стрелке, многоугольник может быть и невыпуклым. Решение будет основываться на исп. формулы Пика, однако есть 2 проблемы:...
Ошибка 2094 C++
Задали написать класс, вот собственно он: #pragma hdrstop #pragma argsused #include <iostream.h> #include <tchar.h> #include <stdio.h> class Array { int *a; int n;
Определить количество отрицательных элементов, количество элементов в интервале от 1 до 5 C++
Доброго времени суток. Помогите пожалуйста с задачей.Буду очень благодарна. Даны вещественные массивы c, d.Определить количество отрицательных элементов, количество элементов в интервале от 1 до 5....
C++ Перестроить матрицу Есть матрица 1, 1, 5, 3, 8 4, 1, 6, 4, 4 0, 5, 1, 7, 9 8, 1, 3, 1, 1 9, 9, 1, 2, 9 в матрице надо подсчитать количество одинаковых элементов в каждой строке в данной матрице будет : http://www.cyberforum.ru/cpp-beginners/thread660292.html
C++ Написать две программы на языке С/С++ для расчета значений переменных y и z по заданным формулам http://www.cyberforum.ru/cpp-beginners/thread660289.html
Написать две программы на языке С/С++ для расчета значений переменных y и z по заданным формулам (ссылка ). В первой программе использовать для ввода функцию scanf, для вывода – функцию...
C++ sizeof к объекту или типу? Доброго времени суток! Видел где-то обсуждение, о том к чему надо применять sizeof - к классу или объекту. Мнения были разные, но либо не аргументированные, либо язык их высказываний был для меня... http://www.cyberforum.ru/cpp-beginners/thread660275.html
Thinker
Эксперт С++
4239 / 2213 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.10.2012, 19:08  [ТС] 0

Быстрая проверка натурального числа на простоту

01.10.2012, 19:08. Просмотров 68975. Ответов 111
Метки (Все метки)

Ответ

~OhMyGodSoLong~, про шифрование я уже писал, что там очень большие числа, поэтому эти алгоритмы не применимы там. Просто интересно написать быстрый детерминированный алгоритм для чисел, умещающихся в стандартные типы данных.
ValeryS, немного не то. если числа принадлежат некоторому диапазону (от 1 до R), то решето Эратосфена достаточно построить до корня из R, об этом речь, если для R памяти нет, а для корня из R есть. А иначе алгоритм проверки получится банальным.
При этом никаких лишних циклов не надо, решето Эратосфена до корня из R строится заранее

Добавлено через 7 часов 58 минут
Интересно, но если модуль увеличить, скажем m = 2*3*5*7*11 = 2310, то из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2...\sqrt{n}\} убираются из рассмотрения http://www.cyberforum.ru/cgi-bin/latex.cgi?100% - \frac{480}{2310}\cdot 100% \approx 80% элементов и алгоритм обещает быть быстрее, но есть одно НО... Взаимно простых чисел с модулем m (меньших m) будет 480, которые каждый раз надо на m увеличивать. Это требует использования массива. И такой алгоритм работает медленнее чем три приведенных выше. Поэтому пока третий алгоритм получился самым быстрым. Так что в сторону увеличения модуля (что гарантировало бы использования дополнительной памяти фиксированного размера независимо от тестируемых чисел, что есть хорошо) нет смысла идти.

Вернуться к обсуждению:
Быстрая проверка натурального числа на простоту
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2012, 19:08

Проверка числа на простоту
Помогите написать программу которая проверяет простое число или нет.

Проверка числа на простоту
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители...

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

0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru