Цитата(maxim1000 @ 11.1.2003, 00:05)

если интересно - сходите, например, на www.nature.ru и наберите в поиске "решето Эратосфена"

Или посмотритет тут:
http://forum.vingrad.ru/index.php?showtopic=30076

Может я не вьехал во что-то, но вот фразу:

Цитата

Эта формула даёт все простые числа по порядку начиная с 5. Так же по этой формуле получаются составные числа. Общая доля отсева равна 11/15=0.73333(3).

я не совсем понял... А чем эта формула отличается по смыслу от известной 2^n - 1, там вроде тоже простые получаются числа и составные иногда проскакивают...

Цитата(Dapo @ 10.1.2003, 17:21)

"Я долго коптил, и нашёл закономерность "размножения" простых чисел. "

Есть формула асимптотического распределения простых чисел: p(x) = x/ln x
показывающая, сколько простых числе содержится на интервале 1..x.

Цитата

Общая доля отсева равна 11/15=0.73333(3).

непойму , какой смысл в формуле , если можно легко сделать общую долю отсева 0.5 проверяя только нечетные числа..

Для программной проверки на простоту:
// language C#
int IsProstoe = ...; // Объявляется переменная с числом.
// Проверяется делимость на два. % - деление по модулю.
if ((IsProstoe % 2) == 0)
{
MessageBox.Show ("Не простое!");
}

for (i = 3; i != (IsProstoe / 2); i+2)
{
if ((IsProstoe % i) == 0)
{
MessageBox.Show ("Не простое!");
}
}
Суть действия:
Сначала для быстроты исполнения проверяется на 2. -50% случайных чисел.
Затем идёт перебор для нечётных чисел, больших еденицы и меньших половины числа.
По-моему, хоть это и не самый, возможно, быстрый код, но он надёжен и прост в реализации, а затем будущим программерам в него будет легко въехать (начиная от таких, как я, 10-классников).
Для поиска вводится цикл, в который это помещается.
int MaxProstoe = ...;
for (int IsProstoe = 1; IsProstoe != MaxProstoe)
{...}

Это сообщение отредактировал(а) III.nfo - 19.10.2004, 20:42

Во-первых, 1 - не простое...
Люди не в курсе где можно найти Кнута в электронном виде? А то вы тут его вспоминали...

У меня книжка на винте валяется по криптоанализу. Там вроде метод есть, с помощью которого можно найти простое число нужного порядка. Только там много слов непонятных и не разобрался как это делается.

А по Эратосфену я сам писал. Нашёл все в пределах 80 000 000 000.

У меня даже прога валяется где-то (и работает в пределах 20 минут на 400 МГц). Если интересно...

Помоему этот попроще будет))... И ищет не только в сотне. И в 1000000 нейдёт... всё простые, только немного подождать придётся . Зацените.
Program gen;
uses crt;
var
n,k,t,sum,m: longint;
begin
clrscr;
textcolor (2);
sum:=0;
Read (m);
for n:=1 to m do
begin
t:=1;
k:=2;
while (k<n-1) and (t<>0) do
begin
t:=n mod k;
k:=k+1;
end;
if t=0 then
write ('')
else
begin
Write (' ',n);
inc(sum);
end;
end;
writeLn;
writeLn (sum);
readkey;
end.

Кнута здесь посмотреть  можно

http://www.poiskknig.ru/

Добавлено через 2 минуты и 16 секунд
А можно так, хотя почти тоже самое
Delphi:

Можно, и я свою лепту внесу    
язык Haskell.
Потенциально бесконечная последовательность простых чисел, используется классическое определение простого числа:

Пример взят отсюда.

Потенциально бесконечная последовательность простых чисел, используется решето Эратосфена:

пример мой.

sorry

Еще есть полином Мятисевича (как раз тут и обсуждался) только ничего разумного по нему найти не могу. Кто найдет- дам плюсик )

есть еще косвенные методы) сейчас к примеру иногда используется малая теорема ферма за исключением чисел кармайкла. Только для этого нужны компьютеры побольше   

Это сообщение отредактировал(а) Julius - 10.1.2010, 13:56

этот алгоритм ничем не отличается от самого тривиального алгоритма
b[z] = (a[z]-((i-a[z])/2%a[z]))%a[z] // при проверке на равенство нулю
b[z] = a[z]-((i-a[z])/2%a[z])  // после проверки
(a[z]-((i-a[z])/2%a[z]))%a[z] = 0 <=> 
i-a[z]=0(mod 2*a[z]) <=> 
cуществует такое k (1+2*k - нечётное, чётные можно не проверять), при котором i=a[z]*(1+2*k) 
// % - остаток от деления
если заменить 
if b[z] = 0 then begin
на
if i Mod a[z] = 0 then begin
то алгоритм очевидно будет работать от определения простого числа...

Это сообщение отредактировал(а) ProgBeat - 7.8.2007, 02:07