Нахождение простых чисел. Оптимизация

[German Stimban]

Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 1 до 100.000, на всякий случай напомнив, что простое число - это число, которое делится только на себя и на единицу. Через некоторое время задание было выполнено. Практически все сделали примерно так:

#include <iostream>

bool isProst(int testnum)
{
int counter=0;
for (int i=1;i<=testnum;i++)
if (testnum%i==0)
counter++;
return (!(counter>2));
}

int main()
{
for (int i=1;i<=100000;i++)
if (isProst(i))
std::cout<<i<<"\n";
return 0;
}

Пропустил через команду time, готовая программа выполняется на III-пентиуме 1 минуту и 32 секунды. Поставили задачу, чтобы программа выполнялась как можно быстрее, с прежним алгоритмом и функционалом, изменили до вида:

#include <iostream>
#include <math.h>

bool isProst(int testnum)
{
for (int i=3;i<=sqrt(testnum);i+=2)
if (testnum%i==0)
return false;
return true;
}

int main()
{
std::cout<<2<<"\n";
int tmparr[30000];
int st=0;
for (int i=3;i<=100000;i++)
if (isProst(i))
tmparr[st++]=i;
for (int i=0;i<st;i++)
std::cout<<tmparr[i]<<"\n";
return 0;
}

Программа выполняется на том же компьютере за 1.24 секунды. Результат впечатлил студентов, можно надеяться, что в дальнейшем они будут думать над оптимизацией.

Теперь бы приучить их к красивому коду.

[Rooslan Khayrov]

Мне опять непонятны некоторые принятые здесь решения.
Зачем было заводить временный массив результата? Избегать ввода-вывода, перемежающегося вычислениями? А на что это влияет?
Но если уж завели, можно было бы ещё больше ускорить алгоритм очевидным образом.

[German Stimban]

Зачем было заводить временный массив результата? Избегать ввода-вывода, перемежающегося вычислениями? А на что это влияет?
Да, чтобы вывести на экран все результаты сразу, а не постепенно. Сравнивал скорость работы программы, при постепенном выводе, время выполнения примерно на 25% больше.

Но если уж завели, можно было бы ещё больше ускорить алгоритм очевидным образом.
Указатели? Многопоточность?

[Rooslan Khayrov]

Указатели? Многопоточность?
Нет, просто перебирать делители только из уже найденных простых чисел.
Да, чтобы вывести на экран все результаты сразу, а не постепенно. Сравнивал скорость работы программы, при постепенном выводе, время выполнения примерно на 25% больше.
Это уже шаманство. Даже если эффект действительно наблюдался (я, например, воспроизвести его не могу), мог бы ты объяснить студентам, почему так происходит?
Время, разумеется, надо измерять с перенаправлением вывода в /dev/null, потому что иначе мы меряем скорость рисования в эмуляторе терминала.
И ещё: от hardcoded размеров массивов стоит отучать сразу, потому что неверный выбор чреват расстрелом памяти. Надо было либо воспользоваться теоремой о распределении простых чисел, либо сделать массив динамически расширяемым — вручную или, ещё лучше, использовав std::vector.

[Shuhrat Ismailov]

простое число - это число, которое делится только на себя и на единицу.
небольшая поправочка.
простое число - это натуральное число, большее единицы, которое делится только на себя и на единицу.
Иначе говоря, простое число́— это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя.

[Наташа]

Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 1 до 100.000, на всякий случай напомнив, что простое число - это число, которое делится только на себя и на единицу. Через некоторое время задание было выполнено. Практически все сделали примерно так: Мне кажется это простое не знание алгоритмов, возможно их просто не учили этому -есть огромная куча совершенно различных алгоритмов, к которым просто так не приходят с помощью простой "оптимизации" -их над изучать:)
Например:

List<int> GetPrimNumber(int n)//n -число до которого необходимо искать простые числа
{
//Инициализация
bool[] z = new bool[n+1];
//0 и 1 не простые числа - сразу же исключаем
z[0] = true;
z[1] = true;
double sqrt = Math.Sqrt(n);
int k = 0;
int i = 2; //Первое простое число
while (i <= sqrt)
{
k = i;
while (k*i <= n)
{
z[k*i] = true;
k++;
}
//Поиск нового простого числа
i++;
while ((z[i])&&(i<=sqrt))
{
i++;
}
}
//Все простые числа вносятся в новый список:
List<int> l = new List<int>();
for (int j = 0; j < n+1; j++)
{
if (!z[j]) l.Add(j);
}
return l;//возврат списка с окончательным результатом
}
на c# при n=100 000 выполняется уже за 3 миллисекунды:)

смысл алгоритма очень прост: ряд чисел 2,3,4,5,6,7,8,9,10...,n сначала находим первое не перечеркнутое число 2 и перечеркиваем все кратные ему числа 2,3,4,5,6,7,8,9,10..., ищем следующее не перечеркнутое число -в данном случае 3 и перечеркиваем дополнительно все кратные ему: 2,3,4,5,6,7,8,9,10..., теперь ищем следующее не перечеркнутое ит.д. пока не достигнем числа равного корню из n -все не зачеркнутые числа -простые:) -называеться алгоритм Решето Эратосфена (http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80% D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0)

[Наташа]

еще можно решето А́ткина (http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%90%D1%82% D0%BA%D0%B8%D0%BD%D0%B0) глянуть, это современное оптимизированное Решето Эратосфена -как можно к этому прийти самостоятельно за 2 часа занятий я совершенно себе не представляю...:)

[German Stimban]

Нет, просто перебирать делители только из уже найденных простых чисел.
Если перерабатывать исходный алгоритм, то это лишь усложнит дело. Цель занятия была не изучение популярных алгоритмов, а оптимизация уже готовых.

Это уже шаманство. Даже если эффект действительно наблюдался (я, например, воспроизвести его не могу), мог бы ты объяснить студентам, почему так происходит?
Смог.

Время, разумеется, надо измерять с перенаправлением вывода в /dev/null, потому что иначе мы меряем скорость рисования в эмуляторе терминала.
Руслан, так в том-то и дело, чтобы наглядно показать, что вывод данных на экран, запись данных в файл на диске занимают больше времени, чем процессорные операции.

И ещё: от hardcoded размеров массивов стоит отучать сразу, потому что неверный выбор чреват расстрелом памяти.
Это будет в одном из ближайших занятий. Задам свою любимую задачу - вычислить 2^100.000.

либо сделать массив динамически расширяемым — вручную или, ещё лучше, использовав std::vector.
Это ещё не проходили.

[German Stimban]

Мне кажется это простое не знание алгоритмов, возможно их просто не учили этому -есть огромная куча совершенно различных алгоритмов, к которым просто так не приходят с помощью простой "оптимизации" -их над изучать
Спасибо, буду знать.

[Rooslan Khayrov]

Даже если эффект действительно наблюдался (я, например, воспроизвести его не могу), мог бы ты объяснить студентам, почему так происходит?
Смог.
И как? Повторюсь, у меня этой разницы не наблюдается, что с выводом всего на экран, что в /dev/null. Вариант с массивом даже чуть-чуть медленнее. Значит какими бы ты соображениями это не объяснил, они недостаточно общие.

[German Stimban]

И как? Повторюсь, у меня этой разницы не наблюдается, что с выводом всего на экран, что в /dev/null.Объяснилчто вывод данных на экран, запись данных в файл на диске занимают больше времени, чем процессорные операции.

Вариант с массивом даже чуть-чуть медленнее. Значит какими бы ты соображениями это не объяснил, они недостаточно общие.
Гмм, попробовал то же самое на Мандриве, вариант с массивом работает медленнее. Попробовал на CentOS, вариант с массивом работает шустрее. Это становится интереснее.

[German Stimban]

еще можно решето А́ткина глянуть, это современное оптимизированное Решето Эратосфена -как можно к этому прийти самостоятельно за 2 часа занятий я совершенно себе не представляю..
Наташа только что проводил эксперимент, сравнивал быстродействие двух алгоритмов:
Первый - берётся массив, первый элемент приравнивается двум. Далее в цикле проверяется делимость числа на элементы массива. Если число делится нацело, оно не простое, переходим к следущему. Если элемент массива больше квадратного корня из пробуемого числа, цикл прекращается. Если число простое, оно записывается в массив.
Второй - начальная стадия реализации решета Аткина. Оно выполняется в 2 раза дольше первого варианта.
То есть, решето полезно, если мы хотим узнать является ли данное число простым, но для нахождения последовательности простых чисел оно не является наиболее оптимальным.
Компилятор - GCC

[Shuhrat Ismailov]

То есть, решето полезно, если мы хотим узнать является ли данное число простым, но для нахождения последовательности простых чисел оно не является наиболее оптимальным.
Я, конечно, не спец в программировании, но имею очень хорошую методичку (http://www.natalimak1.narod.ru/prost.htm), которую когда-то рекомендовал студентам.
Там, кроме решета Аткина приведен метод индийского студента Сундарама

Вот что пишет автор:


Ещё одно интересное “решето” для нахождения простых чисел было предложено в 1934 году индийским математиком С. П. Сундарамом. Он придумал очень оригинальную таблицу, состоящую из бесконечного количества бесконечных арифметических прогрессий, причём каждый член первой прогрессии начинает новую прогрессию (с новой строки таблицы). Разностями прогрессий являются все нечётные числа, начиная с 3. (приведен рисунок)
Таблица бесконечно продолжается вправо и вниз. Разность арифметической прогрессии, записанной в первой строке таблицы, равна 3, разность арифметической прогрессии, записанной во второй строке таблицы, равна 5 и т. д. (все нечётные числа подряд являются разностями прогрессий).

Я реализовала метод Сундарама. Вот текст программы, написанный на языке QBASIC:
Программа для решета Сундарама
5 PRINT "VVEDITE M"
7 INPUT M
8 IF INT(M / 2) <> M / 2 THEN 5
9 IF M < 4 THEN 5
10 PRINT "VVEDITE L"
11 INPUT L
12 FOR I = M + 1 TO L STEP 2
15 B = I: A = (B - 1) / 2
17 C = A - 1
20 FOR N = 1 TO C
25 K = (A - N) / (1 + 2 * N)
30 IF INT(K) = K THEN 40
35 NEXT N
36 W = W + 1: PRINT "#"; W
37 PRINT B
40 NEXT I
45 PRINT
50 END
Программа работает очень просто. Надо ввести в программу чётное натуральное число M ≥ 4 и любое натуральное число L > M. Программа выдаст все простые числа в диапазоне от M+1 до L. Недостаток программы: при M = 4 теряются два простых числа: 2 и 3. Но этот недостаток очень легко устранить, если вставить в программу блок простой печати указанных простых чисел в случае, когда M = 4. По этой программе я получила следующий ряд простых чисел в интервале от 5 до 1000 (M = 4, L = 1000):
На форуме dxdy.ru по моей просьбе приведённая программа переписана на двух других языках программирования: Pascal и Turbo C++ 3.0. Вы можете посмотреть эти программы по следующей ссылке:

http://dxdy.ru/post218607.html?sid=6723a4a0d1a58ddd42ca1a8eb19a8f 9c#p218607

В моей реализации решета Сундарама использовано следующее утверждение:
Т Е О Р Е М А
Любое число A, находящееся в таблице Сундарама, может быть представлено в виде: A = (1 + 2 * N) * K + N,
где N – номер строки таблицы, в которой находится данное число, K – порядковый номер числа в этой строке.

[Наташа]

Наташа только что проводил эксперимент, сравнивал быстродействие двух алгоритмов: Первый - берётся массив, первый элемент приравнивается двум. Далее в цикле проверяется делимость числа на элементы массива. Если число делится нацело, оно не простое, переходим к следущему. Если элемент массива больше квадратного корня из пробуемого числа, цикл прекращается. Если число простое, оно записывается в массив. Второй - начальная стадия реализации решета Аткина. Оно выполняется в 2 раза дольше первого варианта.Не очень поняла, что значит:
начальная стадия реализации решета Аткина. Алгоритм он цельный:)
Оно выполняется в 2 раза дольше первого варианта.Попробуйте элементарно увеличить максимальное число до 1 000 000, 10 000 000, 100 000 000, возможно получаться совершенно иные результаты:)
...для нахождения последовательности простых чисел оно не является наиболее оптимальным.Согласна, совершенно оптимальные алгоритмы встречаются чрезвычайно редко, возможно даже еще не открыты, для этого нашего случая:)
То есть, решето полезно, если мы хотим узнать является ли данное число простым, но для нахождения последовательности простых чисел оно не является наиболее оптимальным.Честно говоря, я теряюсь в догадках:) -тот ли алгоритм Аткина /Эратосфена
тестируется:) ведь в этих алгоритмах ничего сказать о произвольном числе n нельзя пока не вычисляться все простые числа от 1 до n:) а для проверки на простоту произвольного числа существуют иные алгоритмы:) т.е. в результате в алгоритме Аткина как и Эратосфена мы должны банально получить все числа за 1 раз, а не проверять каждый раз по одному единственному числу:)

[Наташа]

Вот оно решето Аткина:

static public List<int> GetPrimNumbersAtkin(int num)
{
bool[] isPrimArr = new bool[num + 1];// Инициализация числового ряда
double sqrt = Math.Sqrt(num);
List<int> retList = new List<int>(); //Инициализация списка, простых чисел
int n = 0;
retList.Add(2);//2 и 3 сразу вносятся в список
retList.Add(3);
/*построение прямого произведения для всех чисел x и y
от еденицы до квадратного корня из num */
for (int x = 1; x <= sqrt; x++)
for (int y = 1; y <= sqrt; y++)
{
n = 4 * x * x + y * y;
/* Здесь инвертируются решения для вышестоящего уравнения */
if (((n % 12 == 1) || (n % 12 == 5)) && (n <= num)) isPrimArr[n] = !isPrimArr[n];

n = 3 * x * x + y * y;
if ((n % 12 == 7) && (n <= num)) isPrimArr[n] = !isPrimArr[n];

n = 3 * x * x - y * y;
if ((x>y)&&(n % 12 == 11) && (n <= num)) isPrimArr[n] = !isPrimArr[n];
}
//теперь зачеркиваются все квадраты простых чисел и кратные им числа:
for (int i = 5; i <= sqrt; i++)
if (isPrimArr[i])
for (int k = 1; k*i*i <= num; k++)
{
isPrimArr[k * i * i] = false;
}
//Возвращаться список простых чисел:
for (int i = 5; i <= num; i++)
if (isPrimArr[i]) retList.Add(i);
return retList;
}
на c# :) -Сказочного увеличения производительности по сравнению с решетом Эратосфена не заметила...:)

[German Stimban]

смысл алгоритма очень прост: ряд чисел 2,3,4,5,6,7,8,9,10...,n сначала находим первое не перечеркнутое число 2 и перечеркиваем все кратные ему числа 2,3,4,5,6,7,8,9,10..., ищем следующее не перечеркнутое число -в данном случае 3 и перечеркиваем дополнительно все кратные ему: 2,3,4,5,6,7,8,9,10..., теперь ищем следующее не перечеркнутое ит.д. пока не достигнем числа равного корню из n -все не зачеркнутые числа -простые -называеться алгоритм Решето Эратосфена
Ещё раз хочу сказать "спасибо", Вам, Наталья. Недавно с новой группой дошли до оптимизации алгоритмов и снова на примере простых чисел. В ходе урока раскачался и написал код решения с помощью решета Эратосфена на С++. (если интересно, могу вывести).
В результате максимально оптимизированный "классический" алгоритм
Нет, просто перебирать делители только из уже найденных простых чисел.
искал значения от 1 до 5.000.000 за 5,83 секунд, а Ваш всего за 0,937

[Shuhrat Ismailov]

Решето Сундарама на турбо C++ 3.0
#include <iostream.h>

int main()
{
cout<<"Vvedite m: ";
int m;

cin>>m;
while((int(m/2)==m/2)&&(m>3))
{
cout<<"Vvedite L"<<endl;
int l;
cin>>l;
if(l==0)break;//vihod
double a,k=0.0,c;
int b=0,w=0,t;
for(int i=m+1;i<l;i+=2)
{
b=i;
a=(b-1)/2;
c=a-1;

t=0;
for(double n=1;n<c;n++)
{

k=(a-n)/(1+2*n);

if(int(k)-k==0){t=1;break;}

}

if(t!=1)
{
w++;
cout<<"#"<<" "<<w<<endl;
cout<<b;
}

}
cout<<endl;

}

return 0;
}

[Evgeniy Sklyarevskiy]

искал значения от 1 до 5.000.000 за 5,83 секунд, Герман, найдите заодно, к чему стремится отношение количества простых чисел к количеству просмотренных чисел?

Еще зная, что вероятность того, два числа взаимно просты равна 6/pi^2 можно найти значение Пи! Об этом (и о простых числах) тута http://arbuz.uz/z_pi.html

И еще, раз уж занимаетесь глупостями, то они должны иметь красивый вид © :-0) Нарисуйте Скатерть Улама: все числа выписываются по расширяющейся спирали на клетчатой бумаге (отличное упражнение для новичков!), простые числа отмечаются ярким цветом. Потом смотрите на узор и фигеете! все разговоры о Боге просто отдыхают перед увиденным!

Я делал в древности на Фокспро в текстовом режиме в ДОСе и то впечатляло, попробуйте попиксельно, поглядим, как оно там все у Него устроено...

[German Stimban]

Еще зная, что вероятность того, два числа взаимно просты равна 6/pi^2 можно найти значение Пи!
Не совсем верно, ради разнообразия написал программку.
#include <iostream>
#include <stdlib.h>
#include <math.h>

unsigned long nod(unsigned long a,unsigned long b)
{
if (a<b)
{
unsigned long tmp=a;
a=b;
b=tmp;
}
if (a%b==0) return b;
else return nod(b,a%b);
}

int main()
{
std::cout<<"insert number of iterations: ";
unsigned long a,b,i=0,n,m=0;
std::cin>>n;
while (m++<n)
{
a=random();
b=random();
if (nod(a,b)==1) i++;
}
std::cout<<"Вероятность равна "<<double(i)/n<<"\n";
std::cout<<"Пи квадрат равен "<<6.0*n/i<<"\n";
std::cout<<"Пи равен "<<sqrt(6.0*n/i)<<"\n";
return 0;
}

Результат выполнения следующий (количество итераций - число pi):
100 - 2.94884
1 000 - 3.14918
10 000 - 3.14399
100 000 - 3.14037
1 000 000 - 3.14025
10 000 000 - 3.14142
100 000 000 - 3.1416
1 000 000 000 - 3.14164

[Evgeniy Sklyarevskiy]

Не совсем верно, ради разнообразия написал программку.Классно! Спасибо! Почему не совсем верно, работает же, приближается к Пи, причем, то сверху то снизу сужаясь!!!!
Миллиард итераций дало три (почти четыре :-0) ) знака после запятой!

Особенно невероятно это потому, что Пи происходит из геометрии, а тут чистая теория чисел, не имеющая отношения к геометрии и тоже выходит на Пи!

И напоминаю про Скатерть Улама, у кого есть время машинное!

[JackDaniels]

Интересно было бы поставить задачу по числам Мерсенна, и профит не плохой и задача не тривиальная. :)

[OmoN]

Еще одно решение. До 100 000 работает 1,03-1,04 секунды.
function IsPrime(n:integer):boolean;
var r:boolean;
i:integer;
begin
r := true;
i := 3;
while(i <= sqrt(n))do begin
if((n mod i) = 0)then begin
r := false;
break;
end;
i := i+2;
end;
result := r;
end;

procedure FindPrimes(maxNumber:integer);
var i: integer;
label lab;
begin
i := 3;
WriteLn('BEGIN');
WriteLn('2');
WriteLn('3');
while(i<=maxNumber)do begin
if(i>3)and(i mod 3 = 0)then goto lab;
if(i>5)and(i mod 5 = 0)then goto lab;
if(i>7)and(i mod 7 = 0)then goto lab;
if(((i-1) mod 6)*((i+1) mod 6) = 0)and(i>3) then
if(IsPrime(i))then WriteLn(i);
lab:
i := i+2;
end;
WriteLn('END');
end;

[Evgeniy Sklyarevskiy]

До 100 000 работает 1,03-1,04 секунды. И как там Пи? чему равно по новым данным?

[Rooslan Khayrov]

И напоминаю про Скатерть Улама, у кого есть время машинное!
Да пожалуйста:
https://gist.github.com/970169
import Data.List
import Graphics.Gloss
import Graphics.Gloss.Data.Point

infixl 6 |+|

(x, y) |+| (x', y') = (x + x', y + y')

spiral = scanl (|+|) (0, 0) steps
where
steps = concat $ zipWith replicate sides (iterate r90ccw (1, 0))
sides = concatMap (replicate 2) $ map fromIntegral [1..]
r90ccw (x, y) = (-y, x)

primes :: [Int]
primes = 2 : 3 : filter isPrime [5, 7 ..]
where
isPrime n = and [n `mod` i /= 0 |
i <- takeWhile (\i -> i * i <= n) (tail primes)]

primesMask = merge [1..] primes
where
merge (n : nt) ps@(p : pt)
| n == p = True : merge nt pt
| otherwise = False : merge nt ps

side = 600

picture = color black $ pictures $ [translate x y (rectangleSolid 1 1) |
(x, y) <- takeWhile isVisible $ filteredSpiral]
where
filteredSpiral = map fst $ filter snd $ zip spiral primesMask
isVisible p = pointInBox p (side, side) (-side, -side)

main = displayInWindow "Ulam spiral" windowSize (100, 100) white picture
where windowSize = (round side, round side)

Алгоритм наивный, не решето, но на помещающихся в экран объёмах и такой справляется.
https://img.uforum.uz/thumbs/tysprsu6596752.png (https://img.uforum.uz/images/tysprsu6596752.png)

[Evgeniy Sklyarevskiy]

Да пожалуйста: Отлично, спасибо!

Теперь осталось объяснить происхождение явно выделенных диагональных отрезков и мы в дамках! :-0)

[Наташа]

В ходе урока раскачался и написал код решения с помощью решета Эратосфена на С++. (если интересно, могу вывести). В результате максимально оптимизированный "классический" алгоритмДа, конечно выкладывайте:)

[Наташа]

Теперь осталось объяснить происхождение явно выделенных диагональных отрезков и мы в дамках! :-0)
Видимо в прямой зависимости от потраченных в пустую часов и богатства фантазии можно усмотреть так же и вертикальные и горизонтальные линии и даже цветочки и прочее разное...:)

[Evgeniy Sklyarevskiy]

Видимо в прямой зависимости от потраченных в пустую часов и богатства фантазии можно усмотреть так же и вертикальные и горизонтальные линии и даже цветочки и прочее разное... Хотите сказать, что диагональные под 45 градусов линии я придумал? Рассмотрите крупно картинку, они там есть! Гарднер объяснял это семейством простых чисел, порождаемых уравнениями вроде x^2 + x + 41 - дает подряд много простых чисел, лежащих на диагонали. Объяснить эту визуализацию каких-то закономерностей пока никто не может.

[JackDaniels]

Видимо в прямой зависимости от потраченных в пустую часов и богатства фантазии можно усмотреть так же и вертикальные и горизонтальные линии и даже цветочки и прочее разное... Хотите сказать, что диагональные под 45 градусов линии я придумал? Рассмотрите крупно картинку, они там есть! Гарднер объяснял это семейством простых чисел, порождаемых уравнениями вроде x^2 + x + 41 - дает подряд много простых чисел, лежащих на диагонали. Объяснить эту визуализацию каких-то закономерностей пока никто не может.

Да, это не просто белый шум, в нем явно прослеживаются четкие диагонали.

[Evgeniy Sklyarevskiy]

Мы на пороге великого открытия, осталось самую малость.... проследить и объяснить :-0)

[JackDaniels]

Мы на пороге великого открытия, осталось самую малость.... проследить и объяснить :-0)

Да мы вечно на пороге, уж переступить бы…

[Evgeniy Sklyarevskiy]

Да мы вечно на пороге, уж переступить бы… Давайте пока подумаем что будем делать с премией за великое открытие?

[JackDaniels]

Да мы вечно на пороге, уж переступить бы… Давайте пока подумаем что будем делать с премией за великое открытие?

Потратим на велосипеды :biggrin:

[Shuhrat Ismailov]

Рассмотрите крупно картинку, они там есть! Гарднер объяснял это семейством простых чисел, порождаемых уравнениями вроде x^2 + x + 41 - дает подряд много простых чисел, лежащих на диагонали.
Эта формула не видна на скатерти Улама. Чтобы ее увидеть, нужно в качестве начального числа спирали выбрать 41. Тогда отчетливо получится прямая, содержащая 40 последовательных простых чисел. Воспользуйтесь простенькой программой на русском языке для всяческих экспериментов с визуализацией

[Evgeniy Sklyarevskiy]

Воспользуйтесь простенькой программой на русском языке для всяческих экспериментов с визуализацией Спасибо, занятная штука!

[German Stimban]

В ходе урока раскачался и написал код решения с помощью решета Эратосфена на С++. (если интересно, могу вывести). В результате максимально оптимизированный "классический" алгоритмДа, конечно выкладывайте:)

Решето Эратосфена, до 5 миллионов считает 0.45 секунд.
#include <iostream>
int main()
{
int size=5000000;
bool num[size];
for (int i=0;i<size;i++)
num[i]=true;
num[0]=num[1]=false;
for (int i=2;i<size;i++)
{
if (num[i])
{
int count=2;
while (i*count<size)
num[i*count++]=false;
}
}
for (int i=2;i<size;i++)
if (num[i])
std::cout<<i<<"\n";
return 0;
}

Решето Сур(не помню как дальше), немного модернизированное, до 5 миллионов считает 1.7 секунд.
#include <iostream>

int main()
{
int size=5000000;
bool isPrime[size];
for (int i=0;i<=size;i++)
isPrime[i]=(i%2==1);
isPrime[0]=isPrime[1]=false;
for (int i=3;i<=size/3;i+=2)
for (int j=3;j<=size/i;j+=2)
isPrime[i*j]=false;
for (int i=0;i<=size;i++)
if (isPrime[i]) std::cout<<i<<endl;
}

[Наташа]

Решето Эратосфена, до 5 миллионов считает 0.45 секунд.Да, это оно самое..:)
Можно попробовать и сюда внести уже преложенные Вами улучшения (http://uforum.uz/showthread.php?p=493282&postcount=1)
возможно это чуточку ускорило бы его:)
Например
for (int i=2;i<size;i++)

заменить на
for (int i=2;i<sqrt(size);i++)

а так же
int count=2;
заменить на
int count=i;

Ваш замечательный алгоритм мог бы выглядить например так:

#include <iostream>
int main()
{
int size=5000000;
bool num[size];
for (int i=0;i<size;i++)
num[i]=true;
num[0]=num[1]=false;
for (int i=2;i<sqrt(size);i++)
{
if (num[i])
{
int count=i;
while (i*count<size)
num[i*count++]=false;
}
}
for (int i=2;i<size;i++)
if (num[i])
std::cout<<i<<"\n";
return 0;
}

[Evgeniy Sklyarevskiy]

for (int i=2;i<sqrt(size);i++)
Может лучше <sqrt(size+1) на всякий случай? Чтобы не пропустить числа близкие к корню.

[German Stimban]

Можно попробовать и сюда внести уже преложенные Вами улучшения
возможно это чуточку ускорило бы его
Например
for (int i=2;i<size;i++)

заменить на
for (int i=2;i<sqrt(size);i++)
а так же
int count=2;
заменить на
int count=i;
Ваш замечательный алгоритм мог бы выглядить например так:
Спасибо большое, глаз замылился и я проглядел. Ускорение почти в 2 раза.