《算法竞赛入门经典》最大孪生素数是指在给定范围内的最大的m和稍微次之的m-2的两个素数
代码:
#include <stdio.h> #include <math.h> #include <assert.h> int is_prime(int n) { int i, m; assert(n > 0 && n < 10000); //检查输入的合法性 if (n == 1) return 0; m = floor(sqrt(n)+0.5); //直接向上取整,避免截断 for ( i = 2; i <= m; i++) if (n % i == 0) return 0; //not prime return 1; //is prime } int main() { int m; scanf("%d", &m); m = m-2; //不减掉2也是可以的,但下面的while的条件要改为 m>=5,m-2改为m+2。因为最小的孪生素数就是3和5了 while (m >= 3) { if (is_prime(m) && is_prime(m+2)) { //一旦找到最大孪生素数,就退出 printf("%d, %d", m, m+2); break; } m--; } return 0; }
测试:
输入:10000
输出:9929, 9931