![]() |
|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Пользователь
Регистрация: 20.12.2009
Сообщений: 40
|
![]()
Проверка большого нат. числа на простоту
Простое число это число которое делится только на само себя и на единицу. Большое число - например 16549875629787. Я как понимаю число надо записывать в строковый массив, потом делить столбиком на все числа от 2 до введенного. При этом делать проверку на остаток от деления. Проблема заключается в реализации деления столбиком. Почитав несколько форумов, я примерно понял как должен выглядеть алгоритм, а вот с программной реализацией парюсь уже третий час и ничего хорошего написать не удалось. Помогите пожалуйста! |
![]() |
![]() |
![]() |
#2 |
Я
Форумчанин
Регистрация: 24.04.2010
Сообщений: 693
|
![]()
Если будешь делить столбиком, проверка будет длиться очень долго. У меня есть реализованный на С++ алгоритм Миллера-Рабина с использованием технологии GMP, числа порядка 10^1200 проверяет несколько секунд
Код:
Все персонажи вымышлены, все совпадения случайны.
Если жизнь игра, тогда я её разработчик ©. |
![]() |
![]() |
![]() |
#3 |
Я
Форумчанин
Регистрация: 24.04.2010
Сообщений: 693
|
![]()
Есть еще пример без использования GMP, но там код огромный, да и разобраться в нем будет не просто
Все персонажи вымышлены, все совпадения случайны.
Если жизнь игра, тогда я её разработчик ©. |
![]() |
![]() |
![]() |
#4 |
Пользователь
Регистрация: 20.12.2009
Сообщений: 40
|
![]()
Я в этом даже разобратся не могу(((
Код:
Это просто деление без поиска простоты. На шаге "if (A[j] < Y[j])" пишет что индекс находится вне границ массива. Не могу понять почему(. |
![]() |
![]() |
![]() |
#5 |
Пользователь
Регистрация: 20.12.2009
Сообщений: 40
|
![]()
уже исправил
Код:
хотя пока правильно не делит( |
![]() |
![]() |
![]() |
#6 |
Пользователь
Регистрация: 20.12.2009
Сообщений: 40
|
![]()
Полагаю что Z[i]++ я поместил не туда, вот только куда надо.....
|
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Перевод в строку большого числа | RIO | Общие вопросы C/C++ | 0 | 23.05.2010 23:51 |
корень из большого числа BigInteger | motorway | Общие вопросы .NET | 5 | 09.12.2009 11:35 |
корень произвольной степени из большого числа с помощью BCMath | motorway | PHP | 8 | 25.09.2009 18:50 |
Изменения данных большого числа ячеек | NDEV | Microsoft Office Excel | 2 | 21.11.2008 13:49 |
Си наити факториал большого числа и вывести в виде массива | Владимир #include | Помощь студентам | 2 | 28.10.2008 13:13 |