质数 AcWing 866. 试除法判定质数

雨点打透心脏的1/2处 2023-09-28 11:33 126阅读 0赞

## 质数 AcWing 866. 试除法判定质数 ##

### 原题链接 ###

[AcWing 866. 试除法判定质数][AcWing 866.]

### 算法标签 ###

数学知识 质数试 除法

### 思路 ###

对于 < 2 <2 <2的数， 一定非质数  
对于 > = 2 >=2 >=2的数若 n n n不是质数， 设 d d d为该数的一个分解因子， 则 n / d n/d n/d为与 d d d一对儿的分解因子， 由于 d ∗ d = = n d\*d==n d∗d==n 得  d < = s q r t ( n ) d<=sqrt(n) d<=sqrt(n) 因此试除法判定质数查找因子范围为 2 − s q r t ( n ) 2-sqrt(n) 2−sqrt(n)

### tips ###

d < = s q r t ( n ) d<=sqrt(n) d<=sqrt(n)  
问题 每次循环计算sqrt(n) 而sqrt计算耗时  
 i ∗ i < = n i\*i<=n i∗i<=n  
若 i i i为 i n t int int型最大值 则 i + 1 i+1 i\+1有数据范围超限风险  
综上 i < = n / i i<=n/i i<=n/i规避上述问题

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    const int N = 100005;
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    bool isp(int n){
        if(n<2){
            return false;
        }
        for(int i=2;i<=n/i;++i){
            if(!(n%i)){
                return false;
            }
        }
        return true;
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	int n=read();
    	while(n--){
    	    int a=read();
    	    if(isp(a)){
    	        puts("Yes");
    	    }else{
    	        puts("No");
    	    }
    	}
    	return 0;
    }

这里  
原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 866.]: https://www.acwing.com/problem/content/868/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png