Salve volevo chiedervi se mi sapreste aiutare nel calcolare la complessità temporale di questo esercizio? Se possibile anche il ragionamento che è stato fatto. Grazie mille in anticipo. 🙈 🙈 🙈
C++:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> set;
vector<int> primo;
int NumPrim(int x)
{
int rad = sqrt(x);
for (int i = 2; i <= rad; i++)
if (x % i == 0)
return 0;
return 1;
}
void print()
{
int n = set.size();
for (int i = 0; i < n; i++)
cout << set[i] << " ";
cout <<endl;
}
void Somma(int totale, int N, int S, int index)
{
if (totale == S && set.size() == N)
{
print();
return;
}
// ci fermiamo se il totale è maggiore di S o se l'indice ha raggiunto l'ultimo elemento
if (totale > S || index == primo.size())
return;
set.push_back(primo[index]);
Somma(totale+primo[index], N, S, index+1);
set.pop_back(); //backtrack
Somma(totale, N, S, index+1);
}
void numPrimi(int N, int S, int P)
{
int stop = 0;
for (int i = P+1; i <=S ; i++) // andiamo a creare il vettore dei numeri primi da P a S
{
if (NumPrim(i) == 1)
primo.push_back(i);
}
if (primo.size() < N)
return;
Somma(0, N, S, 0);
}
int main()
{
int t;
cin>>t;
while(t--){
int S,N,P;
cin>>S>>N>>P;
numPrimi(N,S,P);
}
return 0;
}