求不大于 N 的正整数的个数，这些正整数恰好有 9 个正约数。 N<=4*10^(12) c++代码

为了计算小于等于 N 的正整数中有恰好9个正约数的数目，我们可以考虑这种类型的数通常是由两个质数的乘积构成的，因为这样的数会有1（本身）、2（一个质因子）、两个质因子、这两个质因子的乘积以及它们所有可能的互质因数组合形成的。例如，( p^8 \cdot q )，其中 ( p ) 和 ( q ) 是不同的质数。
C++代码可以按照这个思路编写，包括查找质数、检查符合条件的数并计数：
#include <iostream>
#include <vector>
using namespace std;

// Function to check if a number is prime
bool isPrime(int num) {
if (num <= 1)
return false;
for (int i = 2; i * i <= num; ++i) {
if (num % i == 0)
return false;
}
return true;
}

// Function to find the count of numbers with exactly 9 divisors
long long countNineDivisors(int N) {
vector<int> primes;
int p = 2;
while (p * p <= N) {
if (isPrime(p)) {
primes.push_back(p);
for (int i = 0; primes[i] * primes[i] <= N / p; ++i) {
primes.push_back(primes[i] * p);
}
}
p++;
}

long long count = 0;
for (auto&amp; p : primes) {
// For each prime, find its power such that product has exactly 9 divisors
int exponent = 1;
long long prod = pow(p, exponent);
while ((prod + exponent - 1) * (prod + exponent) / 2 == 9 &amp;&amp; prod <= N) {
count += N / prod;
exponent++;
prod *= p;
}
}

return count;
}

int main() {
int N;
cout << "Enter a value for N (<= 4e12): ";
cin >> N;
cout << "Number of integers less than or equal to N with exactly 9 divisors: "
<< countNineDivisors(N) << endl;
return 0;
}
登录后复制