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

@Александр1270 · Регистрация: 13.11.2012

Студворк — интернет-сервис помощи студентам

Найти первое простое число, превосходящее 10^(100).10 в степени 100
как это осуществить в с++?

@Alexxandr · 18.11.2013, 18:47

$https://www.cyberforum.ru/cgi-bin/latex.cgi?10^{100^{100}}$
Много как-то получается ;-(
Можете переформулировать условие?

@Мотороллер · 18.11.2013, 18:49

Сообщение от Alexxandr

Много как-то получается ;-(

мб в этом и задание. длинная арифметика.

@Alexxandr · 18.11.2013, 18:54

Сообщение от Мотороллер

мб в этом и задание. длинная арифметика.

Не по теме:

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

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

@Мотороллер · 18.11.2013, 18:59

Alexxandr, ну я думаю мегабайта хватит для представления такого числа

@SatanaXIII · 18.11.2013, 19:06

Alexxandr, а где вы в этой теме такое число увидели?

@Alexxandr · 18.11.2013, 19:11

Сообщение от SatanaXIII

Alexxandr, а где вы в этой теме такое число увидели?

превосходящее 10^(100).10 в степени 100

Наверно я не так понял ;-(

@Александр1270 · 18.11.2013, 20:31 **[ТС]**

извините.
10 в степени 100

Добавлено через 23 секунды

Сообщение от Александр1270

Найти первое простое число, превосходящее 10^(100).10 в степени 100
как это осуществить в с++?

---
10 в степени 100

Добавлено через 2 минуты
10 в степени 100

@SatanaXIII · 18.11.2013, 20:34

100 в степени 10?

@Александр1270 · 18.11.2013, 21:06 **[ТС]**

Сообщение от SatanaXIII

100 в степени 10?

10 в степени 100

Добавлено через 3 минуты

Сообщение от Alexxandr

Наверно я не так понял ;-(

10 в степени 100

@Liername · 18.11.2013, 21:19

По факту, можно написать класс, содержащий в себе массив char-ок 1000000000000000000000...и т.д...00 элементов, каждый из которых хранит в себе число от 1 до 9. Далее, перегрузить для него математические операторы, дабы он мог складывать, умножать, делить и т.д. это огроменное число (калькулятор длинных чисел).
Правда, время выполнения алгоритма нахождения первого простого числа (будет оооооочень долгий цикл) будет астрономически велико.
Процессоры, способные решать такие задачи в течении времени жизни среднестатистического человека, думаю, появятся не раньше чем через 10 (в степени 100) лет

В общем, задача в любом случае далеко не для новичков. Возможно что у тебя опечатка в том месте, где ты читаешь это задание.

@Alexxandr · 18.11.2013, 23:11

Попробуй алгоритм Соловея — Штрассена, там вроде не надо искать логарифмы от длинных чисел.

@gunslinger · 19.11.2013, 01:13

10^100+267
Как осуществить нахождение? Пока не знаю :-).

@SatanaXIII · 19.11.2013, 08:49

На самом деле ваша задача не так проста как кажется. Во-первых даже в long long int влезет не больше чем $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{18}$ . Следовательно вам нужно использовать длинную арифметику. Во-вторых методом перебора искать простые числа такой величины не хватит имеющейся у вас вычислительной мощности. Почитайте про решето Эратосфена или его более оптимизированные варианты.

Все это по отдельности легко ищется по форуму.

@programina · 19.11.2013, 09:42

Задача очень простая, первое простое число после 10^100 будет число (10^100)+1

Добавлено через 41 минуту

Сообщение от programina

Задача очень простая, первое простое число после 10^100 будет число (10^100)+1

нет, вру.

@gunslinger · 19.11.2013, 14:28

Алгоритм, используемый здесь - http://ru.numberempire.com/primenumbers.php - позволяет проверить число (содержащее не более 128 десятичных знаков) на принадлежность к простым за доли секунд.

@SatanaXIII · 19.11.2013, 14:33

gunslier, алгоритм? Я вижу только табличку.

@gunslinger · 19.11.2013, 15:07

Можно спросить у автора сайта :-).
1. Как уже было сказано, необходимо реализовать работу с большими числами.
2. Проверка, является ли число простым. Есть много примеров, насчет скорости ничего не могу сказать.
На хабре можно поискать.
Например, http://habrahabr.ru/post/133037, http://habrahabr.ru/post/122538.

@salam · 19.11.2013, 15:09

никто это делать быстро и при этом честно не умеет.

@gunslinger · 19.11.2013, 15:23

Хочешь сказать, что на сайте, который я указал в посте №16, есть заранее вычисленные простые числа для интервала от 1 до 10^128-1 и они просто "подставляются" в нужный момент?
Но хранить такую кучу данных как-то нужно.
И что значит "честно"? Число является простым или нет. Третьего варианта нет.
А быстро - хз, какие (и насколько) оптимизированные методы сейчас существуют.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Александр1270 0 / 0 / 0 Регистрация: 13.11.2012 Сообщений: 17

	Найти первое простое число, превосходящее 10^(100) 18.11.2013, 18:36. Показов 4024. Ответов 29 Метки нет (Все метки) Найти первое простое число, превосходящее 10^(100).10 в степени 100 как это осуществить в с++? 0

@Alexxandr 143 / 52 / 17 Регистрация: 12.11.2013 Сообщений: 162
	18.11.2013, 18:47
	$https://www.cyberforum.ru/cgi-bin/latex.cgi?10^{100^{100}}$ Много как-то получается ;-( Можете переформулировать условие? 0

@Мотороллер 435 / 246 / 43 Регистрация: 05.08.2013 Сообщений: 1,670
	18.11.2013, 18:59
	Alexxandr, ну я думаю мегабайта хватит для представления такого числа 0

@SatanaXIII Почетный модератор 5851 / 2862 / 392 Регистрация: 01.11.2011 Сообщений: 6,906
	18.11.2013, 19:06
	Alexxandr, а где вы в этой теме такое число увидели? 0

@SatanaXIII Почетный модератор 5851 / 2862 / 392 Регистрация: 01.11.2011 Сообщений: 6,906
	18.11.2013, 20:34
	100 в степени 10? 0

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

@Alexxandr 143 / 52 / 17 Регистрация: 12.11.2013 Сообщений: 162
	18.11.2013, 23:11
	Попробуй алгоритм Соловея — Штрассена, там вроде не надо искать логарифмы от длинных чисел. 0

@gunslinger place status here 3187 / 2221 / 640 Регистрация: 20.07.2013 Сообщений: 6,017
	19.11.2013, 01:13
	10^100+267 Как осуществить нахождение? Пока не знаю :-). 0

@SatanaXIII Почетный модератор 5851 / 2862 / 392 Регистрация: 01.11.2011 Сообщений: 6,906
	19.11.2013, 08:49
	На самом деле ваша задача не так проста как кажется. Во-первых даже в long long int влезет не больше чем $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{18}$ . Следовательно вам нужно использовать длинную арифметику. Во-вторых методом перебора искать простые числа такой величины не хватит имеющейся у вас вычислительной мощности. Почитайте про решето Эратосфена или его более оптимизированные варианты. Все это по отдельности легко ищется по форуму. 0

@gunslinger place status here 3187 / 2221 / 640 Регистрация: 20.07.2013 Сообщений: 6,017
	19.11.2013, 14:28
	Алгоритм, используемый здесь - http://ru.numberempire.com/primenumbers.php - позволяет проверить число (содержащее не более 128 десятичных знаков) на принадлежность к простым за доли секунд. 0

@SatanaXIII Почетный модератор 5851 / 2862 / 392 Регистрация: 01.11.2011 Сообщений: 6,906
	19.11.2013, 14:33
	gunslier, алгоритм? Я вижу только табличку. 0

@gunslinger place status here 3187 / 2221 / 640 Регистрация: 20.07.2013 Сообщений: 6,017
	19.11.2013, 15:07
	Можно спросить у автора сайта :-). 1. Как уже было сказано, необходимо реализовать работу с большими числами. 2. Проверка, является ли число простым. Есть много примеров, насчет скорости ничего не могу сказать. На хабре можно поискать. Например, http://habrahabr.ru/post/133037, http://habrahabr.ru/post/122538. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	19.11.2013, 15:09
	никто это делать быстро и при этом честно не умеет. 0

@gunslinger place status here 3187 / 2221 / 640 Регистрация: 20.07.2013 Сообщений: 6,017
	19.11.2013, 15:23
	Хочешь сказать, что на сайте, который я указал в посте №16, есть заранее вычисленные простые числа для интервала от 1 до 10^128-1 и они просто "подставляются" в нужный момент? Но хранить такую кучу данных как-то нужно. И что значит "честно"? Число является простым или нет. Третьего варианта нет. А быстро - хз, какие (и насколько) оптимизированные методы сейчас существуют. 0