8 solutions

  • 5
    @ 2022-2-8 16:49:48

    较为基础的题目。

    int n;
    bool prime[1000010];
    
    void ensure_prime() {
      memset(prime, true, sizeof(prime));
      prime[0] = false;
      prime[1] = false;
      for (int i = 2; i <= 1000000; i++) {
        if (!prime[i]) continue;
        for (int j = 2; j <= 1000010; j++) {
          if (i * j < 1000010) prime[i * j] = false;
          else break;
        }
      }
    }
    
    int main() {
      ensure_prime(); // 考虑到数据范围较大,需要提前预计算质数列表
      cin >> n;
      while (n) { // 如果为 0 则退出
        for (int i = 3; i <= 1000010; i += 2) {
          if (prime[i] && prime[n - i]) {
            cout << n << " = " << i << " + " << n - i << endl;
            break;
          }
        }
        cin >> n;
      }
      return 0;
    }
    

    Information

    ID
    197
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    2
    Tags
    # Submissions
    161
    Accepted
    73
    Uploaded By