问题 C: 几乎是素数
传送门:ZWGOJ | 洛谷 UVA10539 | UVA 10539
题目描述
原题面
Almost prime numbers are the non-prime numbers which are divisible by only a single prime number.
In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.
Info
Wikipedia 关于“几乎是素数数”的介绍:Almost prime - Wikipedia
输入要求
First line of the input file contains an integer \(N (N \le 600)\) which indicates how many sets of inputs are there. Each of the next N lines make a single set of input. Each set contains two integer numbers low and high \((0 < low \ge high < 1012)\).
输出要求
For each line of input except the first line you should produce one line of output. This line contains a single integer, which indicates how many almost prime numbers are within the range (inclusive) low . . . high.
样例
1 2 3 4 |
|
1 2 3 |
|
解法
解法和时间复杂度: (1)
- 此处时间复杂度为该解法的算法部分的时间复杂度,不是严谨的整题的时间复杂度
- 埃式筛 + 二分查找 \(O(n\log n)\)
埃式筛 + 二分查找
Warning
注意二分查找中 lower_bound()
和 upper_bound()
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|