P12138题解

· · 题解

P12138

这题蛮简单的

一个正整数只能被 1 和它本身两个数整除，就称为一个质数

众所周知，我们可以循环一个数X的前X-2个数，如果X可以整除这个数，那么它就不是质数，反之它只能被 1 和它本身两个数整除就是质数

可是它如果循环了每一个数太费时了，4%2==4%4 6%3==6%6 5%2==5%4 将一个长X数轴折叠，一一对应的数被X%的值相同

注： x % y （mod）是x除y的余数

无优化代码

bool sushu(int x)
{
    if(x<2)
        return 0;
    for(int i=2;i<x;i++)
        if(x%i==0)
            return 0;
    return 1;
```cpp
bool sushu(int x)
{
    if(x<2)
        return 0;
    for(int i=2;i<x;i++)
        if(x%i==0)
            return 0;
    return 1;
}

优化代码


bool sushu(int x)
{
    if(x<2)
        return 0;
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return 0;
    return 1;
}

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p=0;
bool sushu(int x)
{
    if(x<2)
        return 0;
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
            return 0;
    return 1;
}
signed main()
{
    for(int i=1;;i++)
    {
        if(sushu(i))
        {
            p++;
            if(p==2025)
            {
                cout<<i;
                return 0;
            }
        }
    }
    return 0;
}

输出17609