Форум программистов, компьютерный форум CyberForum.ru

Найти первое простое число, превосходящее 10^(100) - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
Александр1270
0 / 0 / 0
Регистрация: 13.11.2012
Сообщений: 17
18.11.2013, 18:36     Найти первое простое число, превосходящее 10^(100) #1
Найти первое простое число, превосходящее 10^(100).10 в степени 100
как это осуществить в с++?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2013, 18:36     Найти первое простое число, превосходящее 10^(100)
Посмотрите здесь:

Поменять местами в массиве последнее простое число и первое совершенное C++
найти наименьшее целое число вида 2^r превосходящее n C++
C++ Поменять местами в массиве последнее простое число и первое совершенное
Дано простое число. Составить функцию,которая будет находить следующее за ним простое число. C++
C++ Сложить пятнадцатое простое , четвертое совершенное и первое нечетное избыточное число
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Alexxandr
143 / 52 / 7
Регистрация: 12.11.2013
Сообщений: 162
18.11.2013, 18:47     Найти первое простое число, превосходящее 10^(100) #2
http://www.cyberforum.ru/cgi-bin/latex.cgi?10^{100^{100}}
Много как-то получается ;-(
Можете переформулировать условие?
Мотороллер
428 / 240 / 37
Регистрация: 05.08.2013
Сообщений: 1,629
Завершенные тесты: 1
18.11.2013, 18:49     Найти первое простое число, превосходящее 10^(100) #3
Цитата Сообщение от Alexxandr Посмотреть сообщение
Много как-то получается ;-(
мб в этом и задание. длинная арифметика.
Alexxandr
143 / 52 / 7
Регистрация: 12.11.2013
Сообщений: 162
18.11.2013, 18:54     Найти первое простое число, превосходящее 10^(100) #4
Цитата Сообщение от Мотороллер Посмотреть сообщение
мб в этом и задание. длинная арифметика.

Не по теме:

Просто http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{100} - абсолютно нормально, а запись числа, большего http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{{100}^{100}} не влезет даже на все винчестера во Вселенной

Это мне странным и показалось.

Мотороллер
428 / 240 / 37
Регистрация: 05.08.2013
Сообщений: 1,629
Завершенные тесты: 1
18.11.2013, 18:59     Найти первое простое число, превосходящее 10^(100) #5
Alexxandr, ну я думаю мегабайта хватит для представления такого числа
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,332
Завершенные тесты: 1
18.11.2013, 19:06     Найти первое простое число, превосходящее 10^(100) #6
Alexxandr, а где вы в этой теме такое число увидели?
Alexxandr
143 / 52 / 7
Регистрация: 12.11.2013
Сообщений: 162
18.11.2013, 19:11     Найти первое простое число, превосходящее 10^(100) #7
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Alexxandr, а где вы в этой теме такое число увидели?
превосходящее 10^(100).10 в степени 100
Наверно я не так понял ;-(
Александр1270
0 / 0 / 0
Регистрация: 13.11.2012
Сообщений: 17
18.11.2013, 20:31  [ТС]     Найти первое простое число, превосходящее 10^(100) #8
извините.
10 в степени 100

Добавлено через 23 секунды
Цитата Сообщение от Александр1270 Посмотреть сообщение
Найти первое простое число, превосходящее 10^(100).10 в степени 100
как это осуществить в с++?
---
10 в степени 100

Добавлено через 2 минуты
10 в степени 100
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,332
Завершенные тесты: 1
18.11.2013, 20:34     Найти первое простое число, превосходящее 10^(100) #9
100 в степени 10?
Александр1270
0 / 0 / 0
Регистрация: 13.11.2012
Сообщений: 17
18.11.2013, 21:06  [ТС]     Найти первое простое число, превосходящее 10^(100) #10
Цитата Сообщение от SatanaXIII Посмотреть сообщение
100 в степени 10?
10 в степени 100

Добавлено через 3 минуты
Цитата Сообщение от Alexxandr Посмотреть сообщение
Наверно я не так понял ;-(
10 в степени 100
Liername
 Аватар для Liername
1 / 1 / 0
Регистрация: 18.11.2013
Сообщений: 33
18.11.2013, 21:19     Найти первое простое число, превосходящее 10^(100) #11
По факту, можно написать класс, содержащий в себе массив char-ок 1000000000000000000000...и т.д...00 элементов, каждый из которых хранит в себе число от 1 до 9. Далее, перегрузить для него математические операторы, дабы он мог складывать, умножать, делить и т.д. это огроменное число (калькулятор длинных чисел).
Правда, время выполнения алгоритма нахождения первого простого числа (будет оооооочень долгий цикл) будет астрономически велико.
Процессоры, способные решать такие задачи в течении времени жизни среднестатистического человека, думаю, появятся не раньше чем через 10 (в степени 100) лет

В общем, задача в любом случае далеко не для новичков. Возможно что у тебя опечатка в том месте, где ты читаешь это задание.
Alexxandr
143 / 52 / 7
Регистрация: 12.11.2013
Сообщений: 162
18.11.2013, 23:11     Найти первое простое число, превосходящее 10^(100) #12
Попробуй алгоритм Соловея — Штрассена, там вроде не надо искать логарифмы от длинных чисел.
gunslinger
случайный прохожий
 Аватар для gunslinger
1097 / 715 / 184
Регистрация: 20.07.2013
Сообщений: 1,970
19.11.2013, 01:13     Найти первое простое число, превосходящее 10^(100) #13
10^100+267
Как осуществить нахождение? Пока не знаю :-).
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,332
Завершенные тесты: 1
19.11.2013, 08:49     Найти первое простое число, превосходящее 10^(100) #14
На самом деле ваша задача не так проста как кажется. Во-первых даже в long long int влезет не больше чем http://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{18}. Следовательно вам нужно использовать длинную арифметику. Во-вторых методом перебора искать простые числа такой величины не хватит имеющейся у вас вычислительной мощности. Почитайте про решето Эратосфена или его более оптимизированные варианты.

Все это по отдельности легко ищется по форуму.
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
19.11.2013, 09:42     Найти первое простое число, превосходящее 10^(100) #15
Задача очень простая, первое простое число после 10^100 будет число (10^100)+1

Добавлено через 41 минуту
Цитата Сообщение от programina Посмотреть сообщение
Задача очень простая, первое простое число после 10^100 будет число (10^100)+1
нет, вру.
gunslinger
случайный прохожий
 Аватар для gunslinger
1097 / 715 / 184
Регистрация: 20.07.2013
Сообщений: 1,970
19.11.2013, 14:28     Найти первое простое число, превосходящее 10^(100) #16
Алгоритм, используемый здесь - http://ru.numberempire.com/primenumbers.php - позволяет проверить число (содержащее не более 128 десятичных знаков) на принадлежность к простым за доли секунд.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5548 / 2562 / 233
Регистрация: 01.11.2011
Сообщений: 6,332
Завершенные тесты: 1
19.11.2013, 14:33     Найти первое простое число, превосходящее 10^(100) #17
gunslier, алгоритм? Я вижу только табличку.
gunslinger
случайный прохожий
 Аватар для gunslinger
1097 / 715 / 184
Регистрация: 20.07.2013
Сообщений: 1,970
19.11.2013, 15:07     Найти первое простое число, превосходящее 10^(100) #18
Можно спросить у автора сайта :-).
1. Как уже было сказано, необходимо реализовать работу с большими числами.
2. Проверка, является ли число простым. Есть много примеров, насчет скорости ничего не могу сказать.
На хабре можно поискать.
Например, http://habrahabr.ru/post/133037, http://habrahabr.ru/post/122538.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
19.11.2013, 15:09     Найти первое простое число, превосходящее 10^(100) #19
никто это делать быстро и при этом честно не умеет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.11.2013, 15:23     Найти первое простое число, превосходящее 10^(100)
Еще ссылки по теме:

Дано простое число. Составить функцию, которая будет находить следующее за ним простое число C++
Как найти первое простое число, превосходящее 10^100? C++
C++ Дано простое число. Составить функцию, которая будет находить следующее за ним простое число.

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
gunslinger
случайный прохожий
 Аватар для gunslinger
1097 / 715 / 184
Регистрация: 20.07.2013
Сообщений: 1,970
19.11.2013, 15:23     Найти первое простое число, превосходящее 10^(100) #20
Хочешь сказать, что на сайте, который я указал в посте №16, есть заранее вычисленные простые числа для интервала от 1 до 10^128-1 и они просто "подставляются" в нужный момент?
Но хранить такую кучу данных как-то нужно.
И что значит "честно"? Число является простым или нет. Третьего варианта нет.
А быстро - хз, какие (и насколько) оптимизированные методы сейчас существуют.
Yandex
Объявления
19.11.2013, 15:23     Найти первое простое число, превосходящее 10^(100)
Ответ Создать тему
Опции темы

Текущее время: 10:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru