Недавно у одного известного исполнителя появилась новая песня. Он хочет загрузить её в VK Музыку. Перед пиар-менеджером встала задача — выбрать длительность в секундах для трека,…

Задача сводится к таким числам: числа с не более чем 3 делителями это 1, простые числа и квадраты простых чисел. Нужно посчитать, сколько таких чисел лежит в диапазоне [L, R], где L = max(1, t − d), R = t + d.

Чтобы посчитать в диапазоне до 1e7 элементов количество простых чисел и квадратов простых, удобно использовать сегментированный решет. Нужно:

• Найти все простые числа до sqrt(R) (потому что чтобы проверить простой в диапазоне [L, R], достаточно делителей до sqrt(R)).
• Применить сегментированный решет по диапазону [L, R], пометив составные числа.
• Посчитать количество простых в диапазоне.
• Посчитать количество квадратов простых p^2 в диапазоне, перебрав простые p до sqrt(R) и считав те, чьи квадраты попадают в [L, R].
• Учесть число 1, если оно попадает в диапазон.

Код на Java:

import java.io.*;
import java.util.*;

/*
  Решение: подсчитываем числа с не более чем 3 делителями в диапазоне [L, R],
  где L = max(1, t - d), R = t + d.
  Такие числа: 1, primes, и p^2 (поскольку d(n) = 3 для n = p^2, p - простое).
*/
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if (line == null || line.trim().isEmpty()) return;
        StringTokenizer st = new StringTokenizer(line);
        long t = Long.parseLong(st.nextToken());
        long d = Long.parseLong(st.nextToken());

        long L = t - d;
        if (L < 1) L = 1;
        long R = t + d;

        int limit = (int) Math.floor(Math.sqrt((double) R)); // sqrt(R)

        // Сначала находим все простые до limit
        boolean[] isPrimeSmall = new boolean[limit + 1];
        Arrays.fill(isPrimeSmall, true);
        if (limit >= 0) isPrimeSmall[0] = false;
        if (limit >= 1) isPrimeSmall[1] = false;
        for (int i = 2; (long) i * i <= limit; i++) {
            if (isPrimeSmall[i]) {
                for (int j = i * i; j <= limit; j += i) isPrimeSmall[j] = false;
            }
        }
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++) {
            if (isPrimeSmall[i]) primes.add(i);
        }

        // Сегментированное решето для [L, R]
        int len = (int) (R - L + 1);
        boolean[] segPrime = new boolean[len];
        Arrays.fill(segPrime, true);

        for (int p : primes) {
            long lp = p;
            long start = Math.max(lp * lp, ((L + p - 1) / p) * lp);
            if (start > R) continue;
            for (long x = start; x <= R; x += lp) {
                segPrime[(int) (x - L)] = false;
            }
        }

        // Момент: 1 не является простым
        if (L == 1) segPrime[0] = false;

        long countPrimesInSegment = 0;
        for (int i = 0; i < len; i++) {
            if (segPrime[i]) {
                long val = L + i;
                if (val >= 2) countPrimesInSegment++;
            }
        }

        // Подсчет чисел p^2 внутри [L, R], где p — простое
        long countPrimeSquares = 0;
        for (int p : primes) {
            long sq = (long) p * p;
            if (sq > R) break;
            if (sq >= L) countPrimeSquares++;
        }

        // Учет числа 1, если оно в диапазоне
        long total = 0;
        if (L <= 1 && 1 <= R) total += 1;
        total += countPrimesInSegment;
        total += countPrimeSquares;

        System.out.println(total);
    }
}

Пояснения по сложности:

• Построение простых до sqrt(R): O(limit log log limit), limit ≈ 7.1e6.
• Сегментированное sieve на диапазон длины до 2d+1 ≤ 1e7: около O(range log log limit) операций.
• Подсчет квадратов простых до sqrt(R): до порядка количества primes до sqrt(R) (~ 4–5 сотен тысяч), что быстро.

Этот подход подходит для условий задачи: t ≤ 5·10^13, d ≤ 5·10^6.