题目69：找出一百万以下的n中使得n/φ(n)取到最大的n

永恒的蓝色梦想

C++ 12ms

1. #include<iostream>
   
2. #include<vector>
   
3. #include<cstring>
   
4. using namespace std;
   
5. 
   
6. 
   
7. 
   
8. template<size_t size, typename T>
   
9. void euler_sieve(bool (&is_prime)[size], vector<T>& primes, T (&phi)[size]) {
   
10.     T i, k;
    
11.     memset(is_prime, -1, size);
    
12.     is_prime[0] = is_prime[1] = 0;
    
13. 
    
14.     for (i = 2; i < size; i++) {
    
15.         if (is_prime[i]) {
    
16.             primes.push_back(i);
    
17.             phi[i] = i - 1;
    
18.         }
    
19. 
    
20.         for (T j : primes) {
    
21.             k = i * j;
    
22. 
    
23.             if (k >= size) {
    
24.                 break;
    
25.             }
    
26. 
    
27.             is_prime[k] = false;
    
28. 
    
29.             if (!(i % j)) {
    
30.                 phi[k] = phi[i] * j;
    
31.                 break;
    
32.             }
    
33. 
    
34.             phi[k] = phi[i] * (j - 1);
    
35.         }
    
36.     }
    
37. }
    
38. 
    
39. 
    
40. 
    
41. int main() {
    
42.     ios::sync_with_stdio(false);
    
43. 
    
44.     constexpr unsigned int UPPER_BOUND = 1000000;
    
45.     static bool is_prime[UPPER_BOUND];
    
46.     static unsigned int phi[UPPER_BOUND];
    
47.     vector<unsigned int> primes;
    
48.     double max_div = 0, div;
    
49.     unsigned int max_n = 0, n;
    
50. 
    
51.     euler_sieve(is_prime, primes, phi);
    
52. 
    
53. 
    
54.     for (n = 2; n < UPPER_BOUND; n++) {
    
55.         div = (double)n / phi[n];
    
56. 
    
57.         if (div > max_div) {
    
58.             max_div = div;
    
59.             max_n = n;
    
60.         }
    
61.     }
    
62. 
    
63. 
    
64.     cout << max_n << endl;
    
65.     return 0;
    
66. }

复制代码