最大孪生素数

时间:2021-11-12 11:08:47

《算法竞赛入门经典》最大孪生素数是指在给定范围内的最大的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

^_^ THE END