Untitled
unknown
plain_text
a year ago
1.5 kB
2
Indexable
Never
#include <iostream> #include<vector> using namespace std; bool prime[100000]; vector<int> primes; void primelist(){ for (int i=0;i<100000;i++){ prime[i]=true; } prime[0]=false; prime[1]=false; for (int i=2; i<100000; i++){ if (prime[i]){ if((long long)i*i<100000){ for(int m=i*i; m<100000; m+=i) prime[m] = false; } primes.push_back(i); } } } int bit_sum(int num){ int sum=0; while(num){ sum+=num%10; num/=10; } return sum; } int prime_sum(int num){ int sum=0,i=0; while(primes[i]<=num&&i<primes.size()){ while(num%primes[i]==0){ sum+=bit_sum(primes[i]); num/=primes[i]; } i++; } if(num!=1) sum+=bit_sum(num); return sum; } int isprime(int num){ int i=0; while(i<primes.size()&&primes[i]<num){ if(num%primes[i]==0){ return 0; } i++; } return 1; } int findsmith(int number){ for (int i=number+1;i<1e-9;i++){ if(isprime(number)) continue; if(prime_sum(i)==bit_sum(i)){ return i; } } } int main() { primelist(); int t,n; cin>>t; while(t--){ cin>>n; cout<<findsmith(n)<<endl; } return 0; }