Нужна помощь о сито эратосфена в бесплатном паскале

Question

Мой учитель дал мне это:

п<=10^6;

массив из n целых чисел:ai..an(ai<=10^9);

найти все простые числа.

он сказал кое-что о сите из эратосфена, и я читал об этом, а также о факторизации колеса, но я все еще не мог понять, как заставить программу (fpc) ​​работать в 1 с.?? насколько я знаю, это невозможно, но все же хочу узнать ваше мнение. и с факторизацией колеса, круг 2*3 будет рассматривать 25 как простое число, и я хочу спросить, есть ли способ найти первое число колеса, которое считается неправильным как простое число. пример: круг 2*3*5, как найти первое составное число, рассматриваемое как простое число?? пожалуйста, помогите.. и извините за плохой английский.

Answer 1

Правильное сито Эратосфена должно найти простые числа менее миллиарда примерно за секунду; возможно. Если вы покажете нам свой код, мы будем рады помочь вам найти, что не так.

Наименьший составной элемент, не отмеченный колесом 2,3,5, равен 49: следующий по величине простой элемент, не являющийся членом колеса, равен 7, а 7 * 7 = 49.

Answer 2

Я сделал это сейчас, и он находит простые числа до 1000000 за несколько миллисекунд, без отображения всех этих чисел. Объявите массив a из n + 1 bools (если он начинается с нуля). В начале 0-й и 1-й элементы являются ложными, все остальные верны (ложь не является простым). Алгоритм выглядит так:

i = 2;
while i * i <= n
    if a[i] == true
        j = i * i;
        while j < n
            a[j] = false;
            j = j + i;
    i = i + 1;

В цикле условие i * i <= n, потому что вы начинаете поиск по i * i (меньшие простые числа, чем было найдено уже одним из других простых чисел), поэтому квадратный корень из i не должен быть больше n. Вы удаляете все числа, которые умножаются на простые числа до n. Временная сложность O(n log log n). Если вы хотите отобразить простые числа, вы отображаете индексы, значения в массиве которых являются истинными.

Факторизация полезна, если вы хотите найти, например, все полупростые числа от 0 до n (произведения двух простых чисел). Затем вы найдете все наименьшие простые делители от 0 до n/2 и проверите для каждого числа, имеет ли он простой делитель и имеет ли число, деленное на его простой делитель, делители нуля. Если это так - это полупростая. Моя программа писала так, что она вычисляла в 8 раз быстрее, чем сначала находила все простые числа, а затем умножала их и сохраняла результат в массиве.