4739. Решето Эратосфена

По заданным целым числам a и b выведите все простые числа в интервале от a до b включительно.

Вход. Два целых числа a и b (1 ≤ a ≤ b ≤ 10⁵).

Выход. Выведите в одной строке все простые числа в интервале от a до b включительно.

Пример входа	Пример выхода
1 10	2 3 5 7

РЕШЕНИЕ

решето Эратосфена

Анализ алгоритма

Используя алгоритм решета Эратосфена, заполним массив primes, в котором

· primes[i] = 1, если i простое;

· primes[i] = 0, если i составное;

Выведем все числа i на промежутке от a до b, для которых primes[i] = 1.

Пример

Заполненный массив primes имеет вид:

Простыми числами на промежутке [1; 10] будут 2, 3, 5, 7.

Реализация алгоритма

Объявим рабочий массив primes.

#define MAX 100001

int primes[MAX];

Функция gen_primes реализует решето Эратосфена. Заполняем массив primes. Числа 0 и 1 не простые.

void gen_primes(void)

{

int i, j;

for (i = 0; i < MAX; i++) primes[i] = 1;

primes[0] = primes[1] = 0;

for (i = 2; i * i <= MAX; i++)

if (primes[i])

for (j = i * i; j < MAX; j += i) primes[j] = 0;

}

Основная часть программы. Заполняем массив primes.

gen_primes();

Читаем входные данные.

scanf("%d %d", &a, &b);

Выводим все простые числа от a до b.

for (i = a; i <= b; i++)

if (primes[i]) printf("%d ", i);

printf("\n");

Реализация алгоритма – bitset

Объявим переменную primes типа bitset для хранения информаци о простых числах.

#define MAX 100001

bitset<MAX> primes;

Функция gen_primes реализует решето Эратосфена. Заполняем массив primes. Числа 0 и 1 не простые.

void gen_primes(void)

{

primes.flip(); // set all to 1

primes.reset(0); primes.reset(1);

for (int i = 2; i <= sqrt(MAX); i++)

if (primes.test(i))

for (int j = i * i; j < MAX; j += i) primes.reset(j);

}

Основная часть программы. Заполняем массив primes.

gen_primes();

Читаем входные данные.

scanf("%d %d", &a, &b);

Выводим все простые числа от a до b.

for (i = a; i <= b; i++)

if (primes.test(i)) printf("%d ", i);

printf("\n");

Java реализация

import java.util.*;

public class Main

{

final static int MAX_SIZE = 100001;

static BitSet bits = new BitSet(MAX_SIZE);

public static void Eratosthenes()

{

bits.set(2, MAX_SIZE, true);

for (int i = 2; i < Math.sqrt(MAX_SIZE); i++)

{

if (bits.get(i))

for (int j = i * i; j < MAX_SIZE; j += i)

bits.set(j, false);

}

}

public static void main(String args[])

{

Scanner con = new Scanner(System.in);

Eratosthenes();

int a = con.nextInt();

int b = con.nextInt();

for (int i = a; i <= b; i++)

if (bits.get(i)) System.out.print(i + " ");

System.out.println();

con.close();

}

}

Python реализация

Функция seive_of_eratosthenes реализует решето Эратосфена. Заполняем и возвращаем список is_prime. Числа 0 и 1 не простые.

def seive_of_eratosthenes(n):

is_prime = [True] * (n+1)

is_prime[0], is_prime[1] = False, False

for i in range(2, int(n ** 0.5) + 1):

if is_prime[i]:

for j in range(i * i, n + 1, i):

is_prime[j] = False

return is_prime

Основная часть программы. Заполняем массив prime.

prime = seive_of_eratosthenes(100000)

Читаем входные данные.

a, b = map(int, input().split())

Выводим все простые числа от a до b.

for i in range (a, b + 1):

if prime[i]: print(i,end=' ')