思路

• 一个数恰有三个因子当且仅当它是某个素数的平方：$n = p^2$。

  • 若 $n=p^2$，其因子为 $1,p,p^2$ 共 $3$ 个。
  • 若有恰好 $3$ 个因子，则其素因子分解必须是 $p^2$ 的形式。

• 因此，区间 $[l,r]$ 内伪质数的个数等于满足 $p^2 \in [l,r]$ 的素数 $p$ 的个数。

• 令 $A=\lfloor \sqrt{r} \rfloor$，$B=\lfloor \sqrt{l-1} \rfloor$，答案为

  $$\pi(A) - \pi(B),$$

  其中 $\pi(x)$ 表示不超过 $x$ 的素数个数。

• 由于 $r \le 10^{14}$，只需预处理所有 $\le 10^7$ 的素数（$10^7 = \sqrt{10^{14}}$）。

• 预处理：用埃氏筛得到所有素数列表，然后用二分统计 $\le A$ 与 $\le B$ 的素数个数。

• 复杂度：筛法时间 $O(N \log\log N)$（$N=10^7$），每次查询二分 $O(\log \pi(N))$，空间 $O(N)$。

C++

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;

// 整数平方根：返回 floor(sqrt(n))
static inline ull isqrt(ull n) {
	long double d = sqrtl((long double)n);
	ull x = (ull)d;
	// 调整以防浮点误差
	while ((__int128)(x + 1) * (x + 1) <= n) ++x;
	while ((__int128)x * x > n) --x;
	return x;
}

// 埃氏筛：生成 [2..limit] 的所有素数
static vector<int> sieve_primes(int limit) {
	vector<char> comp(limit + 1, 0);
	vector<int> primes;
	if (limit >= 2) primes.push_back(2);
	for (int i = 3; i <= limit; i += 2) {
		if (!comp[i]) {
			primes.push_back(i);
			if ((long long)i * i <= limit) {
				for (long long j = 1LL * i * i; j <= limit; j += 2LL * i) {
					comp[(size_t)j] = 1;
				}
			}
		}
	}
	return primes;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	const int LIMIT = 10000000; // sqrt(1e14)
	vector<int> primes = sieve_primes(LIMIT);

	int T;
	if (!(cin >> T)) return 0;
	while (T--) {
		ull l, r;
		cin >> l >> r;

		ull A = isqrt(r);
		ull B = (l == 0 ? 0 : isqrt(l - 1)); // 题中 l>=1，但写成通用
		// 统计 <=A 与 <=B 的素数数量（upper_bound）
		auto cntA = upper_bound(primes.begin(), primes.end(), (int)A) - primes.begin();
		auto cntB = upper_bound(primes.begin(), primes.end(), (int)B) - primes.begin();
		cout << (cntA - cntB) << "\n";
	}
	return 0;
}

python

import sys
from math import isqrt
from bisect import bisect_right

# 埃氏筛，返回素数列表
def sieve_primes(limit: int):
    # 使用 bytearray 节省内存
    comp = bytearray(limit + 1)
    primes = []
    if limit >= 2:
        primes.append(2)
    # 只筛奇数
    for i in range(3, limit + 1, 2):
        if not comp[i]:
            primes.append(i)
            if i * i <= limit:
                step = 2 * i
                start = i * i
                comp[start:limit + 1:step] = b'\x01' * (((limit - start) // step) + 1)
    return primes

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    T = int(next(it))
    LIMIT = 10_000_000  # sqrt(1e14)
    primes = sieve_primes(LIMIT)

    out_lines = []
    for _ in range(T):
        l = int(next(it)); r = int(next(it))
        A = isqrt(r)
        B = isqrt(l - 1) if l > 0 else 0
        cntA = bisect_right(primes, A)
        cntB = bisect_right(primes, B)
        out_lines.append(str(cntA - cntB))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

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

public class Main {
	static final int LIMIT = 10_000_000; // sqrt(1e14)
	static int[] primes;
	static int pcnt;

	// 快速输入
	static class FastScanner {
		private final InputStream in;
		private final byte[] buffer = new byte[1 << 16];
		private int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = is; }
		private int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		long nextLong() throws IOException {
			int c; long sgn = 1, val = 0;
			do { c = read(); } while (c <= 32);
			if (c == '-') { sgn = -1; c = read(); }
			while (c > 32) {
				val = val * 10 + (c - '0');
				c = read();
			}
			return val * sgn;
		}
		int nextInt() throws IOException { return (int)nextLong(); }
	}

	// 整数平方根：返回 floor(sqrt(n))
	static long isqrt(long n) {
		long x = (long)Math.sqrt((double)n);
		while ((x + 1) * (x + 1) <= n) ++x;
		while (x * x > n) --x;
		return x;
	}

	// 埃氏筛：生成所有素数（存入 primes[]，pcnt 为数量）
	static void sieve() {
		boolean[] comp = new boolean[LIMIT + 1];
		// 预估素数数量 ~ 664579，分配略大以避免扩容
		primes = new int[700_000];
		pcnt = 0;
		if (LIMIT >= 2) primes[pcnt++] = 2;
		for (int i = 3; i <= LIMIT; i += 2) {
			if (!comp[i]) {
				if (pcnt < primes.length) primes[pcnt++] = i;
				if ((long)i * i <= LIMIT) {
					for (long j = 1L * i * i; j <= LIMIT; j += 2L * i) {
						comp[(int)j] = true;
					}
				}
			}
		}
	}

	// 上界二分：返回 <= key 的元素个数
	static int upperBound(int[] a, int n, int key) {
		int lo = 0, hi = n; // [lo, hi)
		while (lo < hi) {
			int mid = (lo + hi) >>> 1;
			if (a[mid] <= key) lo = mid + 1;
			else hi = mid;
		}
		return lo;
	}

	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		sieve();

		int T = fs.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < T; ++t) {
			long l = fs.nextLong();
			long r = fs.nextLong();
			long A = isqrt(r);
			long B = (l > 0) ? isqrt(l - 1) : 0L;

			int cntA = upperBound(primes, pcnt, (int)A);
			int cntB = upperBound(primes, pcnt, (int)B);
			sb.append(cntA - cntB).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

众所周知，质数是指大于 $1$ 且只有 $1$ 及其本身 两个因子的数。

Tk 学习质数后对这种特殊数产生极大的兴趣；

Tk 定义 伪质数 为一个大于 $1$ 并且恰有三个不同正因子的整数；

现在，给定一个闭区间 $[l,r]$ ，Tk 想知道区间中伪质数的个数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数；

此后每组测试数据描述如下：

在一行上输入两个整数 $l,r(1≤l≤r≤ 10^{14})$ ，表示询问区间的左右端点。

输出描述

对于每一组测试数据，新起一行。

输出一个整数，表示区间内伪质数的个数。

样例1

输入

2
1 10
13 15

输出

2
0