素数判断[牛客]

• 1.题目
• 2.分析
• 3.代码
• • 1. 试除法
  • 2. 筛素数+二分查找
• 4.总结
• 5.更新日志

题目链接

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
给你一个整数n, 判断它是否是素数。注意1不是素数。

输入描述:
第一行输入一个整数T,表示需要判断的数的个数
接下来T行每行一个整数n,表示需要判断的数。

1<=n<=1e5,1<=T<=10

输出描述:
输出T行，判断是否是素数。是，输出“Yes”，否则输出“No”

示例1
输入
2
1
2
输出
No
Yes

思路1：试除法判断是否为素数
思路2：先筛出1e5之前的素数，再二分查找即可

素数筛法整理在这里~

#include 
using namespace std;
 
bool is_prime(int n)
{
    if(n<2)
        return false;
    for(int i=2;i<=n/i;i++)
        if(n%i==0)
            return false;
    return true;
}
 
int main()
{
    int n,t;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        if(is_prime(n))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

// 线性筛 + 二分查找 WC
//速度更快了~~~
#include 
using namespace std;

const int N = 1e5;
int pr[N + 10];    //primes
bool st[N + 10];   //state
int cnt;

void primes()
{
    for (int i = 2; i < N; i++)
    {
        if (!st[i]) pr[cnt++] = i; //未筛
        for (int j = 0; pr[j] <= N / i; j++)
        {
            st[pr[j] * i] = true;
            if (i % pr[j] == 0) break;
        }
    }
}


int main()
{
    primes(); //筛
    int t;
    cin >> t;
    int n;
    int l, r, m;
    while (t--)
    {
        scanf("%d", &n);
        l = 0, r = cnt - 1;
        while (l < r)
        {
             //写法1：
             // m= l + r + 1 >> 1;
             //if (n < pr[m]) r = m - 1;
             //else l = m;     //防止l=m=r-1
             
             //写法2：
              m= l + r >> 1;
             if (n > pr[m]) l = m + 1;
             else r = m;
        }
        if (pr[l]==n)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

方法1注意 试除法边界的写法
方法2 注意 筛素数的边界，以及二分查找的边界问题~

2022.6.23 整理上传

欢迎交流、讨论、指正~
不正确、不理解之处欢迎评论留言~