Задача
Пусть $m$ и $n$ $\left(2 ≤ m < n ≤ 107\right)$ — целые числа. Рассмотрим следующее множество:
Prime $\left(m, n\right) = \lbrace{ p | p\;простое, m ≤ p ≤ n \rbrace}$.
Вычислить мощность множества Prime$\left(m, n\right)$.
Входные данные
Состоит из нескольких тестов. Два последовательных теста разделены пустой строкой. Для каждого теста в отдельной строке заданы числа $m$ и $n$.
Выходные данные
Для каждого теста вывести результат в отдельной строке. Результаты соседних тестов разделять пустой строкой. Для каждого теста вывести мощность множества Prime$\left(m, n\right)$.
Тесты
| Входные данные | Выходные данные |
|---|---|
| 2 20
70 110 5 150 |
8
10 33 |
| 7 2056
14 181 27 367 |
307
36 64 |
| 77 777
55 555 33 333 |
116
85 56 |
Код решения
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Arrays; import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); final int MAXN = 10000001; int simple[]=new int[MAXN+1]; for(int i = 2; i <= MAXN; i++){ simple[i] = 1; } for(int i = 2; i <= Math.sqrt(MAXN); i++){ if(simple[i]==1){ for(int j = i * i; j <= MAXN; j += i){ simple[j] = 0; } } } int count[]=new int[MAXN+1]; int lastSum = 0; for(int i = 1; i < MAXN; i++){ count[i] = lastSum + simple[i]; lastSum = count[i]; } while(in.hasNextInt()) { int m = in.nextInt(); int n = in.nextInt(); int answer = count[n] - count[m] + simple[m]; System.out.println(); System.out.println(answer); } } } |
Решение
Для решения этой задачи требуется завести большой массив типа
bool и присвоить ему значение
true. Затем проверяется, простое ли число, если это не так, то присваиваем значение
false.
Затем нужно последовательно сосчитать мощность каждого множества простых чисел, то есть количество простых чисел от
n до
m, с помощью массива-счётчика: записывается в него прошлые и последующие элементы множества простых чисел.
После этого в цикле задаются нужные значения, считается ответ и выводится.