fork(2) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. template <class T> struct GetMax { public: static T const Value; };
  8. template <class T> T const GetMax<T>::Value = string("Not supported!");
  9. template <> int const GetMax<int>::Value = 0x7FFFFFFF;
  10. template <> unsigned int const GetMax<unsigned int>::Value = 0xFFFFFFFFU;
  11.  
  12. template <class T>
  13. class PrimesHelper
  14. {
  15. public:
  16.   PrimesHelper(T max);
  17.   bool isPrime(T n);
  18. private:
  19.   size_t max;
  20.   vector<T> _primes;
  21.   vector<char> _isPrime;
  22.   void calculatePrimes();
  23. };
  24.  
  25. template <class T>
  26. PrimesHelper<T>::PrimesHelper(T max)
  27. {
  28.   this->max = (size_t)(sqrt(max));
  29.   _isPrime.resize(this->max + 1, true);
  30.   _isPrime[0] = _isPrime[1] = false;
  31.   calculatePrimes();
  32. }
  33.  
  34. template <class T>
  35. void PrimesHelper<T>::calculatePrimes()
  36. {
  37.   for (int i = 2; i <= max; i++)
  38.   {
  39.     if (_isPrime[i])
  40.     {
  41.       _primes.push_back(i);
  42.       for (int j = 2 * i; j <= max; j += i)
  43.       {
  44.         _isPrime[j] = false;
  45.       }
  46.     }
  47.   }
  48. }
  49.  
  50. template <class T>
  51. bool PrimesHelper<T>::isPrime(T n)
  52. {
  53.   if (n < 0)
  54.   {
  55.     return false;
  56.   }
  57.  
  58.   if (n <= max)
  59.   {
  60.     return _isPrime[n];
  61.   }
  62.  
  63.   for (size_t i = 0; i < _primes.size(); i++)
  64.   {
  65.     if (n % _primes[i] == 0)
  66.     {
  67.       return false;
  68.     }
  69.   }
  70.  
  71.   return true;
  72. }
  73.  
  74. template <class T>
  75. bool isPrime(T n)
  76. {
  77.   static PrimesHelper<T> primesHelper(GetMax<T>::Value);
  78.   return primesHelper.isPrime(n);
  79. }
  80.  
  81. template <class T>
  82. int addDigits(T n)
  83. {
  84.   int ret = 0;
  85.   while (n > 0)
  86.   {
  87.     ret += n % 10;
  88.     n /= 10;
  89.   }
  90.   return ret;
  91. }
  92.  
  93. void solve(int n, int expectedAnswer =  -1)
  94. {
  95.   int solution = isPrime(addDigits(n));
  96.   if (expectedAnswer != -1 && solution != expectedAnswer)
  97.   {
  98.     cout << "[!!!WRONG ANSWER!!!] ";
  99.   }
  100.  
  101.   cout << (solution ? "yes\n" : "no\n");
  102. }
  103.  
  104. int main()
  105. {
  106.   solve(0, false);
  107.   solve(100, false);
  108.   solve(101, true);
  109.   solve(200, true);
  110.   solve(300, true);
  111.   solve(111, true);
  112.   solve(112, false);
  113.   solve(4, false);
  114.   solve(301, false);
  115.   solve(340, true);
  116.   solve(61, true);
  117.   solve(7, true);
  118.   solve(223, true);
  119.   solve(9992, true);
  120.   solve(9993, false);
  121.   return 0;
  122. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
no
no
yes
yes
yes
yes
no
no
no
yes
yes
yes
yes
yes
no
https://ideone.com/hVt0tf
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!