|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
24.05.2010, 20:32 | #1 |
Пользователь
Регистрация: 20.12.2009
Сообщений: 40
|
Проверка большого нат. числа на простоту
Проверка большого нат. числа на простоту
Простое число это число которое делится только на само себя и на единицу. Большое число - например 16549875629787. Я как понимаю число надо записывать в строковый массив, потом делить столбиком на все числа от 2 до введенного. При этом делать проверку на остаток от деления. Проблема заключается в реализации деления столбиком. Почитав несколько форумов, я примерно понял как должен выглядеть алгоритм, а вот с программной реализацией парюсь уже третий час и ничего хорошего написать не удалось. Помогите пожалуйста! |
25.05.2010, 08:19 | #2 |
Я
Форумчанин
Регистрация: 24.04.2010
Сообщений: 693
|
Если будешь делить столбиком, проверка будет длиться очень долго. У меня есть реализованный на С++ алгоритм Миллера-Рабина с использованием технологии GMP, числа порядка 10^1200 проверяет несколько секунд
Код:
Все персонажи вымышлены, все совпадения случайны.
Если жизнь игра, тогда я её разработчик ©. |
25.05.2010, 08:20 | #3 |
Я
Форумчанин
Регистрация: 24.04.2010
Сообщений: 693
|
Есть еще пример без использования GMP, но там код огромный, да и разобраться в нем будет не просто
Все персонажи вымышлены, все совпадения случайны.
Если жизнь игра, тогда я её разработчик ©. |
30.05.2010, 12:26 | #4 |
Пользователь
Регистрация: 20.12.2009
Сообщений: 40
|
Я в этом даже разобратся не могу(((
Код:
Это просто деление без поиска простоты. На шаге "if (A[j] < Y[j])" пишет что индекс находится вне границ массива. Не могу понять почему(. |
30.05.2010, 21:03 | #5 |
Пользователь
Регистрация: 20.12.2009
Сообщений: 40
|
уже исправил
Код:
хотя пока правильно не делит( |
30.05.2010, 21:04 | #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 |