Простые числа...

SlaMin · Post by **SlaMin** » 11 Mar 2002 23:15

Как-то, на втором курсе кажется, был у нас один препод который написал программку определения простых чисел в диапазоне [0x0,0xFFFF]. Было сказано, что если кто-то напишет быстрее - получит (что-то не помню что <img border="0" title="" alt="[Smile]" src="smile.gif" /> ) автоматом.

Andy77 · Post by **Andy77** » 12 Mar 2002 01:16

а где программка?

SlaMin · Post by **SlaMin** » 12 Mar 2002 02:36

Предлагается предложить свои варианты <img border="0" title="" alt="[Smile]" src="smile.gif" />

CTAC_P · Post by **CTAC_P** » 12 Mar 2002 03:19

Таблица из 65536 значений.

[ 11-03-2002, 18:20: Message edited by: CTAC_P ]

MaxSt · Post by **MaxSt** » 12 Mar 2002 03:57

Yeah, LUTs - rulezzz...

Не, SlaMin, если серьезно - решето Эратосфена это такой примитив...

AK70 · Post by **AK70** » 12 Mar 2002 04:07

<blockquote>quote:<hr />Originally posted by MaxSt:
Yeah, LUTs - rulezzz...

Не, SlaMin, если серьезно - решето Эратосфена это такой примитив...<hr /></blockquote>да, да, перебор, товарищи, только перебор!

SlaMin · Post by **SlaMin** » 12 Mar 2002 04:45

Да, да опустили <img border="0" title="" alt="[Frown]" src="frown.gif" />
Но факт был что двое из нашей группы додумались до того же что и Эратосфен не зная о его трудах <img border="0" title="" alt="[Smile]" src="smile.gif" />

Да кстати у препода было тоже оно самое решето, но автоматы таки получили <img border="0" title="" alt="[Smile]" src="smile.gif" />

[ 11-03-2002, 19:56: Message edited by: SlaMin ]

MaxSt · Post by **MaxSt** » 12 Mar 2002 16:28

Ай-я-яй! Такого дядьку не знать!
Куда молодежь катится (ворчливо)?

FiL · Post by **FiL** » 12 Mar 2002 18:32

<blockquote>quote:<hr />Originally posted by SlaMin:
Да, да опустили <img border="0" title="" alt="[Frown]" src="frown.gif" />
Но факт был что двое из нашей группы додумались до того же что и Эратосфен не зная о его трудах <img border="0" title="" alt="[Smile]" src="smile.gif" /> <hr /></blockquote>А вот Эратосфен не рассказывал когда останавливаться надо. Помнится большая часть примеров виденных где-либо предлагала прокручивать цикл до n/2, хотя нет смысла идти далее sqrt(n). Что там у препода было граничным условием цикла?

SlaMin · Post by **SlaMin** » 12 Mar 2002 18:54

Кроме sqrt(N) там есть еще две вещи:
1. массив из 32768, сразу отбрасывем четные
2. вычеркивание идет умножением n на все невычеркнутые числа не меньше n, т.е. для 7-ми первыми вычекнутыми числами будут 49, 77 и т.д.

Но уважаемая публика решила похвастаться знакомством с Эратосфеном, вместо того чтобы предложить свои варианты <img border="0" title="" alt="[Frown]" src="frown.gif" />

[ 12-03-2002, 10:01: Message edited by: SlaMin ]