题解 | #啊，这居然是个质数#

题目传送门

首先先看题，浓缩一下题目（本来题目就很短），就是输入一个数 ，输出表示 范围内的最大质数。

这道题主要考察的是循环，判断质数的函数的编写以及数据大了之后的时间复杂度问题。

分析完题目后开始写程序，先是定义变量和输入。

long long n;//不开 long long 见祖宗
cin>>n;

接着就是循环从 遍历到 ，这里就有两种写法，楼主都会展示出来。

for(long long i=n;i>=2;i--)
{
	//判断质数
}

while(n>=2)
{
	//判断质数
}

然后就是循环内部。

if(foo(i)==1)//foo()=>判断质数的函数
{
	cout<<i;
	break;
}

再然后就是编写判断质数的函数，先上代码，然后分析。

bool foo(long long n)
{
    if(n==1||n==0)
    {
        return false;
    }
    for(long long i=2;i<=n/i;i++)
    {
        if(n%i==0)
        {
            return false;
        }
    }
    return true;
}

函数内先是特判，小学生都知道 和 既不是质数也不是合数。然后是真正的判断，先是一个循环。

注意！

写此处的时候有的人写的是:

for(long long i=2;i*i<=n;i++)

其他题可以这么写，但是此题不建议这么写，原因：如果 比较大， 超了 范围，那不就 了。

所以正确的写法是：

for(long long i=2;i<=n/i;i++)

时间复杂度的问题解决了，其它的就简单了。

最后是全部代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long n,k,a[N],b[N],ans;
bool foo(long long n)
{
	if(n==1||n==0)
	{
		return false;
	}
	for(long long i=2;i<=n/i;i++)
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	cin>>n;
	for(long long i=n;i>=2;i--)
	{
		if(foo(i)==1)
		{
			cout<<i;
			break;
		}
	}
	return 0;
}