Эффективный алгоритм для получения начал между двумя большими количествами
Я - новичок в C#, я пытаюсь записать приложение для получения начал между двумя номерами, введенными пользователем. Проблема: В больших количествах (верные номера находятся в диапазоне от 1 до 1 000 000 000) занимает много времени получение начал, и согласно проблеме я решаю, целая операция должна быть выполнена в маленьком временном интервале. Это - проблемная ссылка для большего количества объяснения: SPOJ-главный
И вот часть моего кода, это ответственно за получение начал:
public void GetPrime()
{
int L1 = int.Parse(Limits[0]);
int L2 = int.Parse(Limits[1]);
if (L1 == 1)
{
L1++;
}
for (int i = L1; i <= L2; i++)
{
for (int k = L1; k <= L2; k++)
{
if (i == k)
{
continue;
}
else if (i % k == 0)
{
flag = false;
break;
}
else
{
flag = true;
}
}
if (flag)
{
Console.WriteLine(i);
}
}
}
Есть ли какой-либо более быстрый алгоритм?Заранее спасибо.
6 ответов
Я помню, что решал задачу так:
- Используйте сито Эратосфена для генерации всех простых чисел ниже
sqrt(1000000000) = ~32 000в массивеprimes. - Для каждого числа
xмеждуmиnпроверьте, является ли оно простым, проверяя его делимость на числа<= sqrt(x)из массиваprimes. Поэтому дляx = 29вы будете проверять делимость только на2, 3 и 5.
Нет смысла проверять делимость на не простые числа, так как если x делится на не простое y, то существует простое p < y такое, что x делится на p, так как мы можем записать y как произведение простых. Например, 12 делится на 6, но 6 = 2 * 3, а значит, 12 также делится на 2 или 3. Сгенерировав все необходимые простые числа заранее (в данном случае их очень мало), вы значительно сокращаете время, необходимое для фактической проверки на первичность.
Это будет принято и не требует никакой оптимизации или модификации сита, и это довольно чистая реализация.
Вы можете сделать это быстрее, обобщив сито для генерации простых в интервале [слева, справа], а не [2, справа], как это обычно представляется в учебниках и учебниках. Однако это может стать довольно уродливым, и в этом нет необходимости. Но если кому-то интересно, смотрите:
Вы делаете много дополнительных делений, которые не нужны - если вы знаете, что число не делится на 3, нет смысла проверять, делится ли оно на 9, 27 и т. Д. Вы должны стараться делить только на возможные простые множители числа. Кэшируйте генерируемый набор простых чисел и проверяйте только деление на предыдущие простые числа. Обратите внимание, что вам нужно сгенерировать начальный набор простых чисел ниже L1.
Помните, что ни одно число не будет иметь простой множитель, превышающий его собственный квадратный корень, поэтому вы можете прекратить деление на этом этапе. Например, вы можете перестать проверять потенциальные множители числа 29 после 5.
Вы также можете увеличить его на 2, чтобы не проверять, является ли четное число целиком простым (разумеется, с особым регистром для числа 2)
Я задавал этот вопрос во время собеседований - в качестве теста сравнил реализацию, похожую на вашу, с описанным мной алгоритмом. С помощью оптимизированного алгоритма я мог очень быстро сгенерировать сотни тысяч простых чисел - я никогда не беспокоился о том, чтобы ждать медленной и простой реализации.
Вы можете попробовать Решето Эратосфена. Основное отличие будет в том, что вы начнете с L1, а не с 2.
Давайте немного изменим вопрос: как быстро вы можете сгенерировать простые числа между m и n и просто записать их в память? (Или, возможно, на RAM-диск.) С другой стороны, запомните диапазон параметров, описанный на странице проблемы: m и n могут достигать миллиарда, а n-m - не более миллиона.
IVлад и Брайан - наиболее подходящее решение, даже если верно, что более медленное решение может быть достаточно хорошим. Сначала сгенерируйте или даже предварительно вычислите простые числа меньше sqrt (миллиард); их не очень много. Затем выполните усеченное Сито Эратосфена: сделайте массив длиной n-m + 1, чтобы отслеживать статус каждого числа в диапазоне [m, n], причем изначально каждое такое число помечено как простое (1). Затем для каждого предварительно вычисленного простого числа p выполните цикл, который выглядит следующим образом:
for(k=ceil(m/p)*p; k <= n; k += p) status[k-m] = 0;
Этот цикл помечает все числа в диапазоне m <= x <= n как составные (0), если они кратны p. Если это то, что IVlad имел в виду под «довольно некрасивым», я не согласен; Не думаю, что это так уж плохо.
Фактически, почти 40% этой работы приходится только на простые числа 2, 3 и 5. Есть уловка, объединяющая решето для нескольких простых чисел с инициализацией массива состояний. А именно, шаблон делимости на 2, 3 и 5 повторяется по модулю 30. Вместо того, чтобы инициализировать массив всеми единицами, вы можете инициализировать его повторяющимся шаблоном 010000010001010001010001000001. Если вы хотите быть еще более продвинутым, вы можете продвинуться дальше. k на 30 * p вместо p, и отмечать кратные только одним и тем же образцом.
После этого реальный прирост производительности будет включать такие шаги, как использование битового вектора, а не массива символов для хранения данных сита во встроенном кэше. И инициализация битового вектора пословно, а не побитно. Это действительно беспорядочно, а также гипотетически, поскольку вы можете добраться до точки генерации простых чисел быстрее, чем вы можете их использовать. Базовое сито уже очень быстрое и не очень сложное.
Существует множество алгоритмов поиска простых чисел. Одни быстрее, другие проще.
Вы можете начать с самых простых оптимизаций. Например,
зачем вы ищете, если каждое число является простым? Другими словами, уверены ли вы, что, учитывая диапазон от 411 до 418, есть необходимость искать, являются ли числа 412, 414, 416 и 418 простыми? Числа, которые делятся на 2 и 3, можно пропустить с помощью очень простых модификаций кода.
если число не 5, а заканчивается цифрой «5» (1405, 335), оно не простоеплохая идея: это замедлит поиск.как насчет кеширования результатов? Затем вы можете разделить на простые числа, а на каждое число. Более того, рассматриваются только простые числа, меньшие квадратного корня из числа, которое вы ищете.
Если вам нужно что-то действительно быстрое и оптимизированное, альтернативой может быть использование существующего алгоритма вместо того, чтобы изобретать колесо. Вы также можете попытаться найти научные статьи, объясняющие, как это сделать быстро, но это может быть сложно понять и перевести в код.
Одна вещь, о которой никто не упомянул, - это то, что довольно быстро проверить одно число на простоту. Таким образом, если задействованный диапазон невелик, но числа большие (например, генерировать все простые числа от 1 000 000 000 до 1 000 100 000), было бы быстрее просто проверять простоту каждого числа по отдельности.