fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5.  
  6. int sum_digits(int number) {
  7.     int ret = 0;
  8.     do {
  9.         ret += number % 10;
  10.         number /= 10;
  11.     } while (number > 0);
  12.     return ret;
  13. }
  14.  
  15. const bool debug = true;
  16.  
  17. int main() {
  18.  
  19.     int sum, digit;
  20.     std::cin >> sum >> digit;
  21.  
  22.     const int NMAX = (int)1e5;
  23.     std::vector<bool> is_prime(1+NMAX,1);
  24.     is_prime[0] = is_prime[1] = false;
  25.     for (int i = 2; i * i <= NMAX; ++i) {
  26.         if (!is_prime[i]) continue;
  27.         for (int j = i * i; j <= NMAX; j += i) {
  28.             is_prime[j] = false;
  29.         }
  30.     }
  31.  
  32.     if (debug) {
  33.         std::vector<std::vector<int>> cnt(50,std::vector<int>(10,0));
  34.         for (int i = 10000; i <= NMAX; ++i) {
  35.             if (is_prime[i]) cnt[sum_digits(i)][i / 10000]++;
  36.         }
  37.         for (int i = 0; i < 50; ++i) {
  38.             int s = std::accumulate(cnt[i].begin(), cnt[i].end(), 0);
  39.             if (s == 0) continue;
  40.             printf("cnt[%02d]=%3d:", i, s);
  41.             for (int d = 0; d < 10; ++d) {
  42.                 printf(" [%d]=%3d", d, cnt[i][d]);
  43.             }
  44.             printf("\n");
  45.         }
  46.     }
  47.  
  48.     std::vector<int> primes;
  49.     for (int i = 10000; i <= NMAX; ++i) {
  50.         if (is_prime[i] && sum_digits(i) == sum) {
  51.             primes.push_back(i);
  52.         }
  53.     }
  54.  
  55.  
  56.     return 0;
  57. }
Success #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
cnt[04]=  4: [0]=  0 [1]=  1 [2]=  3 [3]=  0 [4]=  0 [5]=  0 [6]=  0 [7]=  0 [8]=  0 [9]=  0
cnt[05]= 12: [0]=  0 [1]=  7 [2]=  4 [3]=  1 [4]=  0 [5]=  0 [6]=  0 [7]=  0 [8]=  0 [9]=  0
cnt[07]= 28: [0]=  0 [1]= 11 [2]= 10 [3]=  3 [4]=  2 [5]=  2 [6]=  0 [7]=  0 [8]=  0 [9]=  0
cnt[08]= 45: [0]=  0 [1]= 19 [2]= 12 [3]=  5 [4]=  4 [5]=  2 [6]=  2 [7]=  1 [8]=  0 [9]=  0
cnt[10]= 95: [0]=  0 [1]= 26 [2]= 24 [3]= 15 [4]= 12 [5]=  9 [6]=  3 [7]=  4 [8]=  1 [9]=  1
cnt[11]=143: [0]=  0 [1]= 46 [2]= 29 [3]= 25 [4]= 15 [5]= 16 [6]=  6 [7]=  2 [8]=  3 [9]=  1
cnt[13]=236: [0]=  0 [1]= 61 [2]= 48 [3]= 43 [4]= 30 [5]= 20 [6]= 15 [7]= 10 [8]=  6 [9]=  3
cnt[14]=272: [0]=  0 [1]= 66 [2]= 51 [3]= 43 [4]= 33 [5]= 23 [6]= 25 [7]= 12 [8]= 13 [9]=  6
cnt[16]=411: [0]=  0 [1]= 85 [2]= 70 [3]= 61 [4]= 46 [5]= 44 [6]= 38 [7]= 25 [8]= 24 [9]= 18
cnt[17]=479: [0]=  0 [1]= 90 [2]= 86 [3]= 77 [4]= 62 [5]= 51 [6]= 39 [7]= 34 [8]= 25 [9]= 15
cnt[19]=630: [0]=  0 [1]=106 [2]= 93 [3]= 88 [4]= 73 [5]= 72 [6]= 58 [7]= 54 [8]= 44 [9]= 42
cnt[20]=664: [0]=  0 [1]= 97 [2]=103 [3]= 84 [4]= 80 [5]= 74 [6]= 68 [7]= 62 [8]= 53 [9]= 43
cnt[22]=742: [0]=  0 [1]= 90 [2]= 83 [3]= 94 [4]= 97 [5]= 79 [6]= 76 [7]= 84 [8]= 76 [9]= 63
cnt[23]=757: [0]=  0 [1]= 89 [2]= 93 [3]=101 [4]= 88 [5]= 88 [6]= 80 [7]= 77 [8]= 73 [9]= 68
cnt[25]=741: [0]=  0 [1]= 75 [2]= 78 [3]= 82 [4]= 84 [5]= 91 [6]= 85 [7]= 88 [8]= 85 [9]= 73
cnt[26]=706: [0]=  0 [1]= 61 [2]= 67 [3]= 65 [4]= 79 [5]= 94 [6]= 87 [7]= 87 [8]= 83 [9]= 83
cnt[28]=580: [0]=  0 [1]= 37 [2]= 50 [3]= 52 [4]= 63 [5]= 65 [6]= 68 [7]= 82 [8]= 82 [9]= 81
cnt[29]=528: [0]=  0 [1]= 32 [2]= 32 [3]= 49 [4]= 54 [5]= 64 [6]= 66 [7]= 72 [8]= 74 [9]= 85
cnt[31]=379: [0]=  0 [1]= 18 [2]= 19 [3]= 26 [4]= 41 [5]= 52 [6]= 46 [7]= 52 [8]= 61 [9]= 64
cnt[32]=341: [0]=  0 [1]=  9 [2]= 17 [3]= 19 [4]= 36 [5]= 34 [6]= 46 [7]= 57 [8]= 58 [9]= 65
cnt[34]=205: [0]=  0 [1]=  3 [2]=  7 [3]= 13 [4]= 15 [5]= 17 [6]= 29 [7]= 34 [8]= 34 [9]= 53
cnt[35]=166: [0]=  0 [1]=  4 [2]=  3 [3]=  9 [4]= 11 [5]= 12 [6]= 23 [7]= 27 [8]= 35 [9]= 42
cnt[37]= 84: [0]=  0 [1]=  0 [2]=  1 [3]=  2 [4]=  3 [5]=  7 [6]=  9 [7]= 16 [8]= 15 [9]= 31
cnt[38]= 62: [0]=  0 [1]=  0 [2]=  0 [3]=  1 [4]=  1 [5]=  7 [6]=  6 [7]= 11 [8]= 16 [9]= 20
cnt[40]= 34: [0]=  0 [1]=  0 [2]=  0 [3]=  0 [4]=  1 [5]=  0 [6]=  2 [7]=  5 [8]= 10 [9]= 16
cnt[41]= 13: [0]=  0 [1]=  0 [2]=  0 [3]=  0 [4]=  0 [5]=  1 [6]=  1 [7]=  5 [8]=  3 [9]=  3
cnt[43]=  4: [0]=  0 [1]=  0 [2]=  0 [3]=  0 [4]=  0 [5]=  0 [6]=  0 [7]=  1 [8]=  2 [9]=  1
cnt[44]=  2: [0]=  0 [1]=  0 [2]=  0 [3]=  0 [4]=  0 [5]=  0 [6]=  0 [7]=  0 [8]=  0 [9]=  2
https://ideone.com/Qs7KCz
language:
C++14 (gcc 8.3)
created:
6 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!