2018/7/31-zznu-oj- 2128: 素数检测 -【费马小定理裸应用】
2024-09-06 18:27:14
2128: 素数检测
时间限制: 1 Sec 内存限制: 128 MB
提交: 84 解决: 32
[提交] [状态] [讨论版] [命题人:admin]
题目描述
在算法竞赛中你会遇到各种各样的有关素数的问题，今天你来解决一个最基础的问题：如何判定一个素数。
对于给定的正整数p，若p非素数，输出-1
若p是素数 输出 ：{sigma(a^(p-1) % p) ，其中a的下界为1，上界为p-1}
即：
对于给定的正整数p，若p非素数，输出-1
若p是素数 输出 ：{sigma(a^(p-1) % p) ，其中a的下界为1，上界为p-1}
即：
输入
多实例测试，每组数据包含一个正整数p（p < 10^16）。
输出
根据情况输出一个正整数，保证答案在int64之内，输出占一行。
样例输入
2
样例输出
1
提示
若一个数有99.9755%以上的概率为素数，你便可以认为这个数字为素数。
大致思路：
利用费马小定理，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），例如：假如a是整数，p是质数，则a,p显然互质(即两者只有一个公约数1)；
那么我们可以得到费马小定理的一个特例，即当p为质数时候， a^(p-1)≡1(mod p)， 这个公式意思就是：a^(p-1) 和1 同时对p 取模的结果是一致的！！！
——百度百科
代码：
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
#include<math.h>
#define N 1008
#define M 100008
using namespace std;
#define ll long long
int prime(ll n){
for(int i=;i<=(int)sqrt(1.0*n) ;i++){
if(n%i==)
return ;
}
return ;
}
int main()
{
ll T; while(scanf("%lld", &T)!=EOF)
{
if(prime(T)==)
printf("-1\n");
else
printf("%lld\n", T-);
} return ;
}
最新文章
- Mac上编译C++报错
- winform对话框控件、打印控件
- 例子：Execution Model Sample - 应用状态保存
- MVC图片验证码
- 【转】总结：2015这一年App Store审核指南都有哪些变化
- Session对象
- Jquery简略API使用
- ng-class用法
- Android Activity之间通信
- 2781: [JSOI2007]文本生成器
- SwaggerAPI注解详解,以及注解常用参数配置
- React Native & Android & iOS & APK
- Java数据结构和算法 - 什么是2-3-4树
- 朱晔和你聊Spring系列S1E9：聊聊Spring的那些注解
- 最好用的js前端框架、组件、文档在线预览插件
- 从GitHub远程仓库中删除文件夹或文件
- Flutter学习之路---------第一个Flutter项目
- Linux-(rcp,scp)
- cocos2d-js中Chipmunk物理引擎相关(1)
- com.alibaba.fastjson.JSONException: default constructor not found. class ……