【大素数判定】最后一次

喜欢ヅ旅行 2024-03-22 10:10 52阅读 0赞

[题目-最后一次 (51nod.com)][-_ _51nod.com]

题意：

![b52b4005a9814b6eb966eb5731cf2189.png][]

思路：

对于多个1e8以上的素数的判定，我们用素数表去判

具体的说，筛出sqrt(N)之内的素数，然后拿N和这些素数比较就好了

如果存在N%prime\[j\]==0，说明N不为素数，否则就是素数

由于素数个数较少，因此这样的做法的复杂度是可以保证的

对于一个大素数区间的筛，参考区间筛，即拿质数表来筛区间大素数

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=1e6+10;
    const int Inf=1e18;
    
    int N,len=0;
    int vis[mxn],prime[mxn];
    
    void p_init(int n){
    	for(int i=2;i<=n;i++){
    		if(!vis[i]) prime[++len]=i;
    		for(int j=1;i<=n/prime[j];j++){
    			vis[i*prime[j]]=1;
    			if(i%prime[j]==0) break;
    		}
    	}
    	//for(int i=1;i<=len;i++) cout<<prime[i]<<" \n"[i==len];
    }
    void solve(){
    	cin>>N;
    	for(int i=N;i>=1;i--){
    		int ok=0;
    		for(int j=1;j<=len;j++){
    			if(i==prime[j]) continue;
    			if(i%prime[j]==0ll){
    				ok=1;
    			}
    		}
    		//if(i==97) cout<<ok<<'\n';
    		if(!ok){
    			cout<<i<<'\n';
    			return;
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	p_init(1e6); 
    	while(__--)solve();return 0;
    }

[-_ _51nod.com]: http://www.51nod.com/Challenge/Problem.html#problemId=2378
[b52b4005a9814b6eb966eb5731cf2189.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/7c936c4a5f0b49af95b750ebce6acd3a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，52人围观）

还没有评论，来说两句吧...

相关阅读

相关【大素数判定】最后一次

[题目-最后一次 (51nod.com)][-_ _51nod.com] 题意： ![b52b4005a9814b6eb966eb5731cf2189.png][] 思路

喜欢ヅ旅行/ 2024年03月22日 10:10/ 0 赞/ 53 阅读

相关素数判定

素数判定对于表达式n^2+n+41,当n在\[x,y\]范围内取整数值时，判定该表达式的值是否都为素数若都为素数，输出OK,否则输出Sorry

我就是我/ 2023年06月17日 10:57/ 0 赞/ 30 阅读

相关素数判定

//素数判定(有问题) /n=1或n太大时请勿调用 n=1时错误判断为素数 n过大时ii可能会溢出/ int isprime(int n) {

我就是我/ 2022年11月26日 01:48/ 0 赞/ 201 阅读

相关【杭电】素数判定

![这里写图片描述][20160720213558691] include<stdio.h> include<math.h> int a[100];

绝地灬酷狼/ 2022年09月23日 14:57/ 0 赞/ 229 阅读

相关 SDUTACM素数判定

题目描述对于表达式n 2\+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x,y<=50)，判定该表达式的值是否都为素数。输入输入数据

阳光穿透心脏的1/2处/ 2022年09月22日 03:57/ 0 赞/ 221 阅读

相关素数判定

素数判定 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述对于表达式n 2\+n+41，当n

我会带着你远行/ 2022年08月10日 04:54/ 0 赞/ 238 阅读

相关 E - 素数判定

E - 素数判定 HPU专题训练（-1）GCD&&素筛&&快速幂\_\_\_\_\_E - 素数判定对于表达式n^2+n+41，当n在（x,y）范围内取整数

短命女/ 2022年06月01日 07:54/ 0 赞/ 266 阅读

相关 HDU2012 素数判定

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

柔光的暖阳◎/ 2022年05月11日 06:40/ 0 赞/ 266 阅读

相关【C语言】素数判定

[【C语言】素数判定][C] 题目：素数判定。编写函数，参数是一个正整数n,如果它是素数，返回1，否则返回0。 > 分析质数概念： > 质数：除了1之外

àì夳堔傛蜴生んèń/ 2022年04月24日 04:50/ 0 赞/ 277 阅读

相关素数判定

include<stdio.h> include<math.h> int prime(int n) { int i; f

青旅半醒/ 2021年11月02日 14:38/ 0 赞/ 385 阅读