fork download
  1. #include <iostream>
  2.  
  3. int primes_all[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
  4.  
  5. const int N_max = 85;
  6. typedef long long ways;
  7. ways ways_to_reach_N[N_max + 1] = { 1 };
  8.  
  9. int main()
  10. {
  11. // find all paths
  12. for( int i = 0; i <= N_max; ++i ) {
  13. ways ways_to_reach_i = ways_to_reach_N[i];
  14.  
  15. if (ways_to_reach_i) {
  16. for( int* p = primes_all; *p <= N_max - i && p < (&primes_all)[1]; ++p ) {
  17. ways_to_reach_N[i + *p] += ways_to_reach_i;
  18. }
  19. }
  20. }
  21.  
  22. // eliminate single-step paths
  23. for( int* p = primes_all; *p <= N_max && p < (&primes_all)[1]; ++p ) {
  24. --ways_to_reach_N[*p];
  25. }
  26.  
  27. // print results
  28. for( int i = 1; i <= N_max; ++i ) {
  29. ways ways_to_reach_i = ways_to_reach_N[i];
  30.  
  31. if (ways_to_reach_i) {
  32. std::cout << i << " -- " << ways_to_reach_i << std::endl;
  33. }
  34. }
  35.  
  36. return 0;
  37. }
  38.  
Success #stdin #stdout 0s 2896KB
stdin
Standard input is empty
stdout
4 -- 1
5 -- 2
6 -- 2
7 -- 5
8 -- 6
9 -- 10
10 -- 16
11 -- 19
12 -- 35
13 -- 45
14 -- 72
15 -- 105
16 -- 152
17 -- 231
18 -- 332
19 -- 500
20 -- 732
21 -- 1081
22 -- 1604
23 -- 2351
24 -- 3493
25 -- 5136
26 -- 7595
27 -- 11212
28 -- 16534
29 -- 24441
30 -- 36039
31 -- 53242
32 -- 78573
33 -- 115989
34 -- 171264
35 -- 252754
36 -- 373214
37 -- 550862
38 -- 813251
39 -- 1200554
40 -- 1772207
41 -- 2616337
42 -- 3862121
43 -- 5701552
44 -- 8416695
45 -- 12424934
46 -- 18342240
47 -- 27077004
48 -- 39972265
49 -- 59007841
50 -- 87109263
51 -- 128593301
52 -- 189832691
53 -- 280237216
54 -- 413693381
55 -- 610706824
56 -- 901542644
57 -- 1330882918
58 -- 1964688666
59 -- 2900328379
60 -- 4281550047
61 -- 6320545914
62 -- 9330572418
63 -- 13774060306
64 -- 20333662070
65 -- 30017140614
66 -- 44312163214
67 -- 65414893801
68 -- 96567348077
69 -- 142555496947
70 -- 210444532770
71 -- 310664269400
72 -- 458611544346
73 -- 677015556294
74 -- 999429852793
75 -- 1475387120370
76 -- 2178008923252
77 -- 3215239478882
78 -- 4746429048795
79 -- 7006815193062
80 -- 10343662267187
81 -- 15269611956240
82 -- 22541440708259
83 -- 33276323565115
84 -- 49123466693303
85 -- 72517475460665