Матч 261, Статистика простых чисел (PrimeStatistics)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Заданы три целых числа: lowerBound, upperBound и modulo. Находятся остатки всех простых чисел, лежащих в промежутке [lowerBound, upperBound] при делении на modulo. Необходимо найти значение чаще всего встречаемого остатка. Если остатков существует несколько, то вывести наименьший.

Класс: PrimeStatistics

Метод: int mostCommonRemainder(int lowerBound, int upperBound,

int modulo)

Ограничения: 1 £ lowerBound, upperBound £ 20000, lowerBound £ upperBound, 2 £ modulo £ 1000.

Вход. Три целых числа: lowerBound, upperBound и modulo.

Выход. Остаток, который чаще всего встречается при делении простых чисел из промежутка [lowerBound, upperBound] на modulo.

Пример входа

lowerBound	upperBound	modulo
3	14	5
3	33	1000
25	27	17

Пример выхода

3

3

0

РЕШЕНИЕ

простые числа

При помощи решета Эратосфена генерируем простые числа от 1 до upperBound в массиве primes. Следует отметить, что единица не является простым числом. Вычисляем остатки от деления всех чисел от lowerBound до upperBound на modulo и заносим их количество в массив rem: число остатков, равных i, содержится в rem[i]. Находим максимальный элемент в массиве rem, его индекс является искомым значением остатка.

Рассмотрим первый пример. Построим массив primes для значений от lowerBound = 3 до upperBound = 14 и найдем остатки от деления простых чисел на modulo = 5.

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14
primes[i]	0	1	1	0	1	0	1	0	0	0	1	0	1	0
primes[i] % modulo	-	-	3	-	0	-	2	-	-	-	1	-	3	-

В массиве rem подсчитываем количество остатков primes[i] % modulo для простых i.

i	0	1	2	3	4
rem[i]	1	1	1	2	0

Максимальное значение массива rem равно 2, чаще всего встречается остаток 3.

ПРОГРАММА

#include <stdio.h>

#include <memory.h>

int max, res, i, j;

int rem[1001], primes[200001];

class PrimeStatistics

{

public:

int mostCommonRemainder(int lowerBound, int upperBound, int modulo)

{

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

primes[1] = 0;

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

if (primes[i])

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

memset(rem,0,sizeof(rem));

for(i = lowerBound; i <= upperBound; i++)

if (primes[i]) rem[i%modulo]++;

for(max = i = 0; i < modulo; i++)

if (rem[i] > max) res = i, max=rem[i];

return res;

}

};