Question

C语言输入一个正整数n,输出大于n但最接近n的5个素数。

Answer 1

问：C语言输入一个正整数n,输出大于n但最接近n的5个素数。

答：请先阅读说明：本题主要考察对于素数的判断以及如何找到下一个素数。对于一个正整数n，大于n的素数可能会非常多，因此本题限定输出最接近n的5个素数。解答思路：首先需要判断一个数是否为素数。一个简单的方法是从2到该数-1逐个判断是否能被该数整除。但这种方法的时间复杂度较高，不太适合本题。更高效的方法是用该数n去除以2到sqrt(n)之间的每个整数，如果都无法整除，则该数为素数。此方法的时间复杂度为O(sqrt(n))。接下来需要找到下一个素数。一个简单的方法是从n+1开始依次判断是否为素数，但这种方法速度较慢。更快的方法是使用“筛选法”：先将2~n范围内所有的数都标记为素数，再从2开始，将其所有的倍数标记为合数（即非素数），最终剩下的就是素数。在找下一个素数时，只需从当前数+1开始逐个判断是否为素数即可。