Решавам проблем, при който ви се дават няколко тестови случая. За всеки случай ви е даден диапазон (от 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++;
}
}