数论——判断素数
1.素数的定义
+ 在数学里，素数指的是大于 $1$ 的正整数中，所有只有 $1$ 和 $n$ 两个因子的数，被称作素数，也叫作质数 + 合数：大于 $1$ 的正整数里，不是质数就是合数 + 三质数：一个平方数开根之后是质数的平方数叫做三质数
2. 判断素数
2.1 判断素数方法1
我们可以想到利用素数的性质来判定素数
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool isprime(int n)
{
if(n<2) return false;
int cnt=0;
for(int i = 1; i <= n; i ++)
{
if(n%i == 0) cnt++; // 求出因子的个数
}
if(cnt==2) return true; // 质数必定是有且仅有两个因子的数
else return false;
}
int main()
{
int x;
while(scanf("%lld", &x)==1)
{
if(isprime(x)) puts("Y");
else puts("N");
}
return 0;
}
这个大家都能明白吧 时间复杂度 $~O(N^2)~$
2.2 判断素数方法2
完全平方数刚刚说过
所有的合数都可以写成$x=y*z$
$a*a=b$，那么$a^2=b$ $b$是完全 平方数
根据反比例函数，可以知道对于所有的合数 $x$，$\min(y, z)$都一定小于等于$\sqrt b$，所以只用枚举到$\sqrt{b}$就可以求出答案了。
小计俩：浮点类型不稳定，使用$\sqrt 4$可能等于$1.999999$，然后枚举到 $1$ 了。所以浮点数可以加上一个$eps$。($eps$的取值范围要注意！一般取值为 $0.001$)
#define int long long
#include <cmath>
const double eps = 0.001;
bool isprime(int x)
{
if(x<2) return false;
double end = 0.001 + sqrt(1. * x);
for(int i = 2; (double)i <= end; i ++)
{
if(x % i == 0) return false;
}
return true;
}
sqrt函数 我自己手写一个看看
double sqrt(double x) // 二分
{
if(x<0) return -1;
double l = 0, r=1E9;
int step=100;
double best = -1.0;
while(step--)
{
double mid=(l+r)/2;
if(mid * mid >= x)
{
best = mid;
r = mid;
}
else
{
l = mid;
}
}
return best;
}
大家注意一下，sqrt 使用的是二分手段，所以时间复杂度$~\approx O(\log N)~$。乘法只用$O(1)$就能解决。所以乘法优化：
#define int long long
#include <cmath>
const double eps = 0.001;
bool isprime(int x)
{
if(x<2) return false;
for(int i = 2; i * i <= x; i ++)
{
if(x % i == 0) return false;
}
return true;
}
时间复杂度：$O(\sqrt N * T)$，T是数据的组数
还是太慢，过不了
怎么办呢？
这个时候就需要使用miller_rabin算法求解了
miller_rabin算法依赖的是费马小定理
$a^n\equiv a$
当然只有 $n$ 是质数的时候才可以 但是，费马小定理是有问题的，是一个假命题，QAQ（遗憾）:cry: 统计表明，在前10亿个自然数中共有50847534个素数，而满足2n-1 ≡ 1 (mod n)的合数n有5597个 如果用费马小定理的逆命题来判断一个正整数n是不是素数，在前10亿个自然数中出错的可能性为0.011% 这个出错的可能性还是很高的，但是仍然可以用这个技巧来排除大量的合数，这种方法就是费马检测 我们可以检测前面的8~12个质数，如果有一个不满足，就返回false，全部满足返回true
这样出错概率 就只有$(\frac{11}{1000})^g$了。(g是检测质数的个数) 在 long long 范围内，经试验，不会出错
但是 有可能越界
使用__int128(洛谷的破绽，noip不允许使用)就能通过
快速乘会超时
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef __int128 il;
int list[8] = {2, 3, 5, 7, 19, 37, 53, 89};
il ksc(long long x, long long y, long long z)
{
il xx = 1;
il answer = xx * x * y % z;
return answer;
// if(y == 0) return 0;
// il w = ksc(x, y/ 2, z);
// w= (w + w) % z;
// if(y & 1)
// {
// w = (w + x) % z;
// }
// return w;
}
long long ksm(long long x, long long y, long long z)
{
if(y == 0) return 1;
il w = ksm(x, y /2 , z);
w= ksc(w, w, z);
if(y & 1)
{
w = ksc(w, x, z);
}
return w;
}
bool miller_rabin(long long n,long long a)
{
long long d = n -1, r = 0;
while((d & 1) == 0)
{
d >>= 1;
r ++;
}
il x = ksm(a, d, n);
if(x== 1)
{
return true;
}
for(int i = 0; i <r ; i ++)
{
if(x == n - 1)
{
return true;
}
x =ksc(x, x, n);
}
return false;
}
bool isprime(long long n )
{
if(n < 2) return false;
for(int a= 0;a< 8; a ++)
{
if(n == list[a])
{
return true;
}
if(n % list[a] == 0)
{
return false;
}
if(! miller_rabin(n, list[a]))
{
return false;
}
}
return true;
}
int main()
{
long long x;
while(scanf("%lld", &x) == 1)
{
if(isprime(x))
{
puts("Y");
}
else
{
puts("N");
}
}
return 0;
}
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
