fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. // Hàm tạo sàng Eratosthenes để tìm tất cả các số nguyên tố <= max_n
  6. vector<bool> sieve(int max_n) {
  7.     vector<bool> is_prime(max_n + 1, true);
  8.     is_prime[0] = is_prime[1] = false;
  9.     for (int i = 2; i * i <= max_n; i++) {
  10.         if (is_prime[i]) {
  11.             for (int j = i * i; j <= max_n; j += i) {
  12.                 is_prime[j] = false;
  13.             }
  14.         }
  15.     }
  16.     return is_prime;
  17. }
  18.  
  19. int main() {
  20.     int n;
  21.     cin >> n;
  22.  
  23.     // Tạo sàng Eratosthenes cho các số <= 2 * n
  24.     vector<bool> is_prime = sieve(2 * n);
  25.  
  26.     // Mảng lưu giá trị g(k) cho k = 2, ..., n
  27.     vector<int> g(n + 1, 0);
  28.  
  29.     // Tính g(k) trước
  30.     for (int k = 2; k <= n; k++) {
  31.         int target = 2 * k;
  32.         for (int p = 2; p <= target / 2; p++) {
  33.             if (is_prime[p] && is_prime[target - p]) {
  34.                 g[k]++;
  35.             }
  36.         }
  37.     }
  38.  
  39.     // Tính f(n) bằng cách cộng dồn g(k)
  40.     int fn = 0;
  41.     for (int k = 2; k <= n; k++) {
  42.         fn += g[k];
  43.     }
  44.  
  45.     cout << fn << endl;
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
15
stdout
copy 
28
https://ideone.com/vFw4Kt
language:
C++14 (gcc 8.3)
created:
5 days 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!