Цитата:
Сообщение от Rooslan Khayrov
(Сообщение 493287)
Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 1 до 100.000, на всякий случай напомнив, что простое число - это число, которое делится только на себя и на единицу. Через некоторое время задание было выполнено. Практически все сделали примерно так:
|
Мне кажется это простое не знание алгоритмов, возможно их просто не учили этому -есть огромная куча совершенно различных алгоритмов, к которым просто так не приходят с помощью простой "оптимизации" -их над изучать:)
Например:
PHP код:
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 -все не зачеркнутые числа -простые:) -называеться алгоритм Решето Эратосфена |
