Лучший способ найти простые множители числа

Я решаю задачу, в которой вам дано несколько тестовых примеров. Для каждого случая вам дается диапазон (от x до y включительно). В пределах этого диапазона я должен посчитать все числа, сумма простых множителей которых точно равна K.

Например:

5 15 2

Мы знаем, что существует 5 чисел, у которых ровно 2 простых делителя (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++;
        }
    }