C程序 检查一个数字是否可以表示为两个素数之和

为了解决这个问题，可以采用“筛法”，即筛选素数，然后枚举其中的两个素数，判断它们的和是否等于给定的数字。

具体步骤如下：

1. 先构造一个数组 marks，用于记录数字是否是素数。这里的实现用到了“埃氏筛法”。

  int marks[MAX_N + 1]; // marks[i] 表示数字 i 是否为素数
  memset(marks, 1, sizeof(marks)); // 先全设置为 true
  marks[0] = marks[1] = 0; // 0 和 1 不是素数
  for (int i = 2; i * i <= MAX_N; i++) {
    if (marks[i]) { // 如果 i 是素数
      // 那么它的倍数都不是素数
      for (int j = i * i; j <= MAX_N; j += i) {
        marks[j] = 0; 
      }
    }
  }

1. 枚举每一个小于等于要判断的数字 n 的素数 i，判断 n-i 是否也是素数，如果是，那么 n 可以表示为两个素数之和。

bool judge(int n) { // 判断 n 是否能表示成两个素数之和
  for (int i = 2; i < n; i++) {
    if (marks[i] && marks[n - i]) { // i 和 n-i 都是素数
      return true;
    }
  }
  return false;
}

1. 进行测试，在主函数中输入一个数字 n，如果 n 可以表示为两个素数之和，输出 "YES"，否则输出 "NO"。

int main() { 
  int n;
  scanf("%d", &n);
  if (judge(n)) {
    printf("YES");
  } else {
    printf("NO");
  }
  return 0;
}

下面是两个示例说明：

1. 输入数字 10，期望输出 "YES"。分析：10 可以表示为 3 和 7 之和，3 和 7 都是素数。

Input: 10
Output: YES

1. 输入数字 20，期望输出 "NO"。分析：20 不可以表示为任意两个素数之和。

Input: 20
Output: NO