给定两个整数 L 和 R，我们的任务是计算范围 [L, R] 内恰好具有 5 个不同正因数的数字个数。
示例：
> 输入： L = 1, R= 100
> 输出： 2
> 解释： 在范围 [1, 100] 中，只有两个数字恰好有 5 个因数，它们是 16 和 81。
> 16 的因数是 {1, 2, 4, 8, 16}。
> 81 的因数是 {1, 3, 9, 27, 81}。
>
>
>
>
>
> 输入： L = 1, R= 100
> 输出： 2
朴素方法： 解决这个问题最简单的方法是遍历范围 [L, R]，对于每一个数字，计算其因数的个数。如果因数的计数等于 5，则将计数增加 1。
时间复杂度： (R – L) × ?N
辅助空间： O(1)
高效方法： 为了优化上述方法，我们需要对恰好有 5 个因数的数字进行以下观察。
> 设一个数字的质因数分解为 p1a1×p2a2 × … ×pnan。
> 因此，这个数字的因数个数可以写成 (a1 + 1)×(a2 + 1)× … ×(an + 1)。
> 因为此乘积必须等于 5（这是一个 质数），所以在乘积中必须只存在一个大于 1 的项。该项必须等于 5。
> 因此，如果 ai + 1 = 5
> => ai = 4
按照以下步骤解决问题：
- 所需计数是范围内包含 p4 作为因数的数字的计数，其中 p 是一个质数。
- 为了高效计算大范围（[1, 1018]）内的 p4，我们的想法是使用 埃拉托斯特尼筛法 来存储所有高达 104.5 的质数。
下面是上述方法的实现：
C++14
// the above approach
#include
using namespace std;
const int N = 2e5;
// Stores all prime numbers
// up to 2 * 10^5
vector prime;
// Function to generate all prime
// numbers up to 2 * 10 ^ 5 using
// Sieve of Eratosthenes
void Sieve()
{
prime.clear();
vector p(N + 1, true);
// Mark 0 and 1 as non-prime
p[0] = p[1] = false;
for (int i = 2; i * i <= N; i++) {
// If i is prime
if (p[i] == true) {
// Mark all its factors as non-prime
for (int j = i * i; j <= N; j += i) {
p[j] = false;
}
}
}
for (int i = 1; i < N; i++) {
// If current number is prime
if (p[i]) {
// Store the prime
prime.push_back(1LL * pow(i, 4));
}
}
}
// Function to count numbers in the
// range [L, R] having exactly 5 factors
void countNumbers(long long int L,
long long int R)
{
// Stores the required count
int Count = 0;
for (int p : prime) {
if (p >= L && p <= R) {
Count++;
}
}
cout << Count << endl;
}
// Driver Code
int main()
{
long long L = 16, R = 85000;
Sieve();
countNumbers(L, R);
return 0;
}
`
Java
`
// Java Program to implement
// the above approach
import java.util.*;
class GFG
{
static int N = 200000;
// Stores all prime numbers
// up to 2 * 10^5
static int prime[] = new int [20000];
static int index = 0;
// Function to generate all prime
// numbers up to 2 * 10 ^ 5 using
// Sieve of Eratosthenes
static void Sieve()
{
index = 0;
int p[] = new int [N + 1];
for(int i = 0; i <= N; i++)
{
p[i] = 1;
}
// Mark 0 and 1 as non-prime
p[0] = p[1] = 0;
for (int i = 2; i * i <= N; i++)
{
// If i is prime
if (p[i] == 1)
{
// Mark all its factors as non-prime
for (int j = i * i; j <= N; j += i)
{
p[j] = 0;
}
}
}
for (int i = 1; i < N; i++)
{
// If current number is prime
if (p[i] == 1)
{
// Store the prime
prime[index++] = (int)(Math.pow(i, 4));
}
}
}
// Function to count numbers in the
// range [L, R] having exactly 5 factors
static void countNumbers(int L,int R)
{
// Stores the required count
int Count = 0;
for(int i = 0; i < index; i++)
{
int p = prime[i];
if (p >= L && p <= R)
{
Count++;
}
}
System.out.println(Count);
}
// Driver Code
public static void main(String[] args)
{
int L = 16, R = 85000;
Sieve();
countNumbers(L, R);
}
}
// This code is contributed by amreshkumar3.
`
Python3
`
# Python3 implementation of
目录
the above approach
N = 2 * 100000
Stores all prime numbers
up to 2 * 10^5
prime = [0] * N
Function to generate all prime
numbers up to 2 * 10 ^ 5 using
Sieve of Eratosthenes
def Sieve() :
p = [True] * (N + 1)
# Mark 0 and 1 as non-prime
p[0] = p[1] = False
i = 2
while(i * i <= N) :
# If i is prime
if (p