#include
#include
#include
using namespace std;
bool primes(int n){
for(int i=2;(i*i)<=n;i++){
if((n%i)==0)
return false;
}
return true;
}
int digitsSum(int n){
int sum=0;
while(n>0){
sum+=n%10;
n=n/10;
}
return sum;
}
bool boston(vector a,int n){
if(binary_search(a.begin(),a.end(),n)){
return false;
}
int dsum=digitsSum(n);
int i=0,sum=0;
for(;i<a.size();i++){
if((n%a[i])==0){
while((n%a[i])==0){
sum=sum+digitsSum(a[i]);
n=n/a[i];
}
}
}
if(dsum==sum) return true;
else return false;
}
int main() {
int n;
cin>>n;
vector sieve;
if(n>=2){
sieve.push_back(2);
}
for(int i=3;i<=n;i++){
if(primes(i)){
sieve.push_back(i);
}
}
// for(int i=0;i<sieve.size();i++){
// cout<<sieve[i]<<" ";
// }
bool ans=boston(sieve,n);
cout<<ans<<’\n’;
}
why tle for 1 test case?
i had tried sieve method also but it gave tle for two test cases ,so i used root(n) approach…