Комментарии 22
Очень похоже на мои попытки https://habr.com/ru/post/333350/
Вычеркнули от 7 по +7
Эм, нет, 49 забыли.
Но в C++ ведь есть словарь - map. В Си можно сделать так:
struct Pair
{
int key;
int value;
};
// еще какой-то код
Pair* pev_primes = malloc(new_size*Pair);
// логика обработки предыдущих простыхКонечно, тут надо оптимизировать -- писал навскидку (Иначе один словарь будет пахнуть квадратичной сложностью).
если мы тащим за собой "мешок" (словарь) уже найденных простых - то мешок неизбежно растет. конечно, можно не тащить, но это будет другая стратегия, и даже возможно другая задача.
исходная задача такая: сделайте Эратосфен (или а ля Эратосфен), но не для фиксированного интервала (а стандартный Эратосфен именно именно об этом), но чтобы найти нужное число простых чисел. дурацкая - не дурацкая, но я встретил именно такую постановку.
я за любую оптимизацию, но надо четко понимать, оптмизация ЧЕГО. самого алгоритма или его имплементации.
Ну да, если мы используем словарь, то он растет. Тут можно, как например, где-то в комментарияхх к этой же статье (или другой), оптимизировать еще через битовые маски и т.д., но принципиально это возможно.
Строго говоря, кстати, стандартный Эратосфен с математической точки зрения, не нуждается в фиксированном интервале -- он применяется ко всему множеству натуральных :). Но я понимаю, о чем вы.
зачем оптимизировать изначально не оптимальный метод?
Есть на много шустрее методы получения простых чисел,
на тех же самых делителях например и без потребления такого объёма памяти
(сохраняем все простые числа в массив, проходимся по каждому натуральному числу и проверяем есть ли у него делитель из прежде найденных, если нет, то добавляем в наш массив, изначально он содержит только 2)
(можно оптимизировать ищя только по простым числам меньше квадратного корня (p*p<n))
Кстати верхняя граница тоже высчитывается математически как интегральный логарифм (см. пи функция)
Простые числа, согласно известному определению – такие числа, которые
делятся только на 1 и само себя. Иначе, число считается составным, и его
можно разложить на произведение простых чисел. Единица формально
соответствует определению простого числа, но это число принято не
относить ни к простым, ни к составным.
Определение не до конца верное. Стоит добавить, что это не просто числа, а натуральные числа, так как без этого уточнения, -7 вполне подходит под определение простого числа.
>> Как построить алгоритм «раздвижного решета» для языка Си или С++?
<< А в чем проблема? Словари (и все "раздвижные" структуры данных) на С пишутся при помощи ссылочек в память. Стандартно описанный во многих учебниках код . Или я чего то не допонял? Решение не доброе тем, что легко выстрелить себе в ногу, но более чем рабочее.
В обычном решете Эратосфена внешний цикл можно делать до корня из maxNum, а внутренний цикл начинать с i * i. Так будет слегка быстрее - процентов на 30.
(единицу, как и договорились, мы сразу выбросим из рассмотрения)
Мы не договаривались
Для Вашего случая подойдет оптимизация решета Эратосфена с запоминанием минимального простого делителя.
В словарь заносятся только произведения текущего числа на простые числа не меньше его минимального простого делителя.
По основной теореме арифметики составное число будет занесено в словарь только один раз.
var primes = new List<int>();
var divisors = new Dictionary<int, int>();
for (int num = 2; ;++num) {
if (divisors.TryGetValue(num, out int divisor){
//составное число
divisors.remove(num);
foreach(int mul in primes){
if (mul > divisor)
break;
divisors[num*mul] = mul;
}
} else {
yield return num;
primes.Add(num);
foreach(int mul in primes){
divisors[num*mul] = mul;
}
}
}
А зачем вообще хранить «последнее удаленное» число если оно вычисляется целочисленным делением ?
Достаточно хранить только сами простые числа, чтобы использовать их в "последующих проходах"
например, на интервале [0..99] вы храните {37:74}
а для интервала от 100 оно элементарно получается как 100//37*37 = 74
«Раздвижное» решето Эратосфена