判断质数【牛客tracker 每日一题】
判断质数
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
给定一个正整数n nn，请判断n nn是否为质数。
【名词解释】
- 质数是指仅能被1 11和其自身整除、且大于1 11的正整数。
输入描述：
在一行上输入一个整数n ( 1 ≦ n ≦ 10 12 ) n(1≦n≦10^{12})n(1≦n≦1012)。
输出描述：
如果n nn为质数，在一行上输出" Y e s " "Yes""Yes"；否则，直接输出" N o " "No""No"。
示例1
输入：
2输出：
Yes说明：
由于2 22仅能被1 11和2 22整除，因此是质数。
示例2
输入：
3输出：
Yes示例3
输入：
4输出：
No说明：
因为4 44可以被2 22整除，因此不是质数。
解题思路
本题核心是试除法判定质数，适配10 12 10^{12}1012的数值范围。根据质数定义，首先处理边界条件：数字1 11不是质数，直接判定为否；数字2 22是唯一的偶质数。对于大于2 22的数，只需遍历2 22到n \sqrt{n}n之间的整数进行取模验证，若存在能整除n nn的数，则n nn为合数；若遍历完成无任何因数，则n nn为质数。由于10 12 = 10 6 \sqrt{10^{12}}=10^61012=106，循环次数仅为10 6 10^6106次，在1 11秒时间限制内可高效完成计算，算法简洁稳定，完美满足题目时间与空间约束。
总结
核心逻辑：利用试除法验证因数，仅需遍历到数字平方根即可完成质数判定。
关键操作：边界值判断、平方根遍历取模、快速判断合数/质数。
效率保障：循环次数控制在10 6 10^6106内，时间空间开销极小，适配大数据范围。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e5+10;constll INF=1e18;constll M=1e6+10;intmain(){ll a;cin>>a;if(a==1){cout<<"No"<<endl;return0;}for(ll i=2;i<=sqrt(a);i++){if(a%i==0){cout<<"No"<<endl;return0;}}cout<<"Yes"<<endl;return0;}