我要解决一个问题，给定一些测试用例。对于每个测试用例，给出一个范围（从x到y，包括边界）。在这个范围内，我必须计算所有质因子之和恰好为K的数字的数量。
例如：
5 15 2
我们知道有5个数字恰好有两个质因数（6、10、12、14和15）。
现在我的代码完全正常，但速度太慢了。我正在寻找一种更快的通过C++生成质数的方法。以下是我的代码。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <math.h>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <deque>
#include <queue>
#define Fill(s, v) memset(s, v, sizeof(s))
#define skipChar() (scanf("%c", &useless));
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar());x=(x<<3)+(x<<1)+_-'0');}while(0)
#define rekt return false;
#define notrekt return true;
char _, useless;
using namespace std;
typedef pair <int, int> intpair;
vector<int> primes;
void sieve(int n){
bool *prime = new bool[n +1];
fill(prime, prime + n+1, true);
prime[0] = false;
prime[1] = false;
int m = sqrt(n);
for(int i = 2; i <= m; i++)
if(prime[i])
for(int k = i*i; k <= n; k+=i){
prime[k] = false;
if(prime[k])primes.push_back(k);
}
for(int i = 0; i <n; i++){
if(prime[i])
primes.push_back(i);
}
}
int main()
{
int t;
int c = 1;
scan(t);
sieve(1000);
while(t--){
int a, b, k;
scan(a);
scan(b);
scan(k);
int realCount = 0;
for(int i = a; i <= b; i++){
int count = 0;
for(int j = 0; j < primes.size(); j++){
if(i % primes[j] == 0){
count++;
}
}
if(count == k)realCount++;
}
cout << "Case #"<< c << ": "<< realCount <<endl;
c++;
}
}
感谢您的帮助！
感谢所有人的贡献！这里是快速和优化的代码！
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <math.h>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <deque>
#include <queue>
#define F(a, s, val) fill(a, a + s, val);
#define skipChar() (scanf("%c", &useless));
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=_=getchar());x=(x<<3)+(x<<1)+_-'0');}while(0)
#define rekt return false;
#define notrekt return true;
char _, useless;
using namespace std;
typedef pair <int, int> intpair;
int *omega = new int[10000001];
void omg(){
for(int i = 2; i < 10000000; i++)
if(omega[i] == 0)
for(int j = i; j < 10000001; j+=i)
omega[j]++;
}
int main(){
int t;
int c = 1;
F(omega, 10000001, 0);
omg();
scan(t);
while(t--){
int a, b, k;
scan(a);
scan(b);
scan(k);
int cc = 0;
for(int i = a; i <= b; i++)
if(omega[i] == k)
cc++;
printf("Case #%i: %i\n", c, cc);
c++;
}
}