Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Для поддержки

Думкин © (2004-07-08 13:22:00)
Необходимо найти 1-й миллион простых чисел и вывести в файл.

Думкин (2004-08-24 06:49:00) [1]
> [19] Mihey_temporary © (23.08.04 23:00)

Да, и на алголисте в форумах об этом идут дебаты.

Mihey_temporary (2004-08-23 23:00:00) [2]
Совсем недавно юзал прогу - надо было просчитать простые числа меньше 100 000 000 000, это где за 3 часа получилось.

Думкин (2004-07-19 12:03:00) [3]
> SergP © (19.07.04 09:15)

Безусловно - 15 485 863

SergP (2004-07-19 09:15:00) [4]

> Пошарься по сайтам олимпиад по информатике. Наверняка есть.
> Интересно, влезает ли миллионное число в unsigned long.

В integer должно по идее влезть....

Aldor_ (2004-07-13 07:19:00) [5]
> попробуйте решетку Диогена

LOL :))) Не сочтите за попытку обидеть, но рассмешили Вы здорово. Так и представил себе Диогена в бочке с решеткой :)
Алггоитм называется "решето Эратосфена".
И если задача стоит "найти _много_ простых чисел", то лучше этого метода пока не существует.
Если же задача "найти _большое_ простое число", то там уже другие методы. В общем, на algolist'e и у Кнута все есть

Думкин (2004-07-12 06:53:00) [6]
> [14] SergP © (12.07.04 02:23)

Угу.

SergP (2004-07-12 02:23:00) [7]

> [13] Думкин © (10.07.04 10:18)
> > [12] Tano (09.07.04 22:13)
>
> При вашем алгоритме есть одна существенная оптимизация.
> Не надо проверять на все найденные до этого. И поверьте
> - вам и дня будет много чтобы найти тоже самое.

Наверное лучше проверять нечетные числа на все найденые до этого в диапазоне от 3 до sqrt(проверяемое число)...

Думкин (2004-07-10 10:18:00) [8]
> [12] Tano (09.07.04 22:13)

При вашем алгоритме есть одна существенная оптимизация. Не надо проверять на все найденные до этого. И поверьте - вам и дня будет много чтобы найти тоже самое.

Tano (2004-07-09 22:13:00) [9]
Я делал простую программу перебора с проверкой на делимость и хранением чисел в памяти.
За неделю часто прерываемой работы оно добралось до 70 млн (комп Athlon XP 1600+)
Алгоритм прост до смешного:
храню массив простых чисел, постепенно увеличивая его длину и каждое нечетное число (что довольно логично) проверяю на делимость на уже найденные простые числа.
Могу готовую прогу переслать.
А самое большое число простое (число Мерсенна) равно
((2 в степени 24,036,583) - 1) и содержит 7 235 733 знаков )))

Думкин (2004-07-09 15:26:00) [10]
а число знаков у Пи уже сотнями миллиардов считается. :-(

Думкин (2004-07-09 15:25:00) [11]

> Я то их много нашел, за 10 лимонов зайдет.

Благо для наших компов, это сейчас совсем просто.
Вот то же число Пи, где-то в 86-м читал, что японцы на супер-пупер посчитали его до 100 000 000 знаков.
А сейчас программы(не моя) его считают за несколько минут на персоналке, мой П-4 за 48 минут справился.
Но ведь самому тоже интересно, не так ли?

Думкин (2004-07-09 15:22:00) [12]

> [8] афвуд (09.07.04 14:13)

Да нет. %-)) Что вы. Миллионное простое очень просто оценивается - что-то около 15 миллионов оно.
Я то их много нашел, за 10 лимонов зайдет. Я новичкам давал, ведь интересно?
А как искать - много способов.
на algolist.manual.ru как-то было как-то в форуме обсуждение и там народ миллиардами вроде хвастался - непрерывными отрезками.

А самое большое найденное - ойё большое.
Кстати для очень больших чисел, если без запаса до подкоренных, про проверку можно прочитать опять же там.

С уважением, извиняюсь за невольный развод. :-)

афвуд (2004-07-09 14:13:00) [13]
А вы не подумали, что возможно самое большое число, из найденных ныне, меньше миллионного простого числа?
Я конечно не знаю точно, но помоему так.

Если так, то пожалей комп, на котором будет работать твоя прога.

Old_monkey (2004-07-09 14:10:00) [14]
Пошарься по сайтам олимпиад по информатике. Наверняка есть.
Интересно, влезает ли миллионное число в unsigned long.

Анонимщик (2004-07-09 12:04:00) [15]
А по формуле (правда, это если можно не подряд)?
Правда, хранить и сохранять не так то просто.

ИдиотЪ (2004-07-09 11:38:00) [16]
попробуйте решетку Диогена

Думкин (2004-07-09 10:58:00) [17]
> [3] NikB (09.07.04 10:37)

Я знаю. Но
1. это я начинающим бросил.
2. Твой способ каков? Если в тупую, стандартно - то поищи - долго будет.
А пооптимальнее? С 10 быстро и не долго думая, а миллион, а 10 миллионов?

NikB (2004-07-09 10:37:00) [18]
сделай алгоритъм с цикл для 10 простьих чисел. Патом промени цикл на 1000000 и все!
ПП
Не забудь записать в файл!

Думкин (2004-07-09 07:34:00) [19]
> [1] Palladin © (09.07.04 00:24)

Пасиба. :)

Palladin (2004-07-09 00:24:00) [20]
Поддерживаю.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »