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

← →
Думкин © (2004-07-08 13:22) [0]

Необходимо найти 1-й миллион простых чисел и вывести в файл.

← →
Palladin © (2004-07-09 00:24) [1]

Поддерживаю.

← →
Думкин © (2004-07-09 07:34) [2]

> [1] Palladin © (09.07.04 00:24)

Пасиба. :)

← →
NikB (2004-07-09 10:37) [3]

сделай алгоритъм с цикл для 10 простьих чисел. Патом промени цикл на 1000000 и все!
ПП
Не забудь записать в файл!

← →
Думкин © (2004-07-09 10:58) [4]

> [3] NikB (09.07.04 10:37)

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

← →
ИдиотЪ (2004-07-09 11:38) [5]

попробуйте решетку Диогена

← →
Анонимщик © (2004-07-09 12:04) [6]

А по формуле (правда, это если можно не подряд)?
Правда, хранить и сохранять не так то просто.

← →
Old_monkey (2004-07-09 14:10) [7]

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

← →
афвуд (2004-07-09 14:13) [8]

А вы не подумали, что возможно самое большое число, из найденных ныне, меньше миллионного простого числа?
Я конечно не знаю точно, но помоему так.

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

← →
Думкин © (2004-07-09 15:22) [9]

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

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

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

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

← →
Думкин © (2004-07-09 15:25) [10]

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

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

← →
Думкин © (2004-07-09 15:26) [11]

а число знаков у Пи уже сотнями миллиардов считается. :-(

← →
Tano (2004-07-09 22:13) [12]

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

← →
Думкин © (2004-07-10 10:18) [13]

> [12] Tano (09.07.04 22:13)

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

← →
SergP © (2004-07-12 02:23) [14]

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

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

← →
Aldor_ (2004-07-13 07:19) [16]

> попробуйте решетку Диогена

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

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

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

Совсем недавно юзал прогу - надо было просчитать простые числа меньше 100 000 000 000, это где за 3 часа получилось.

Для поддержки Найти похожие ветки