素数的定义:如果一个大于1的正整数n只有1和它本身这两个因子,那么n是素数,否则n是合数。1不是素数也不是合数。
求素数的几种方法,复杂度从大到小:
试除法
对于一个整数n,如果区间[2, \sqrt(n)]
内不存在n的因子,那么n是质数。因为一个数的因子中除了其算术平方根外,都是成对出现的,且不可能存在两个大于\sqrt(n)
的因子(显而易见)。那么使用试除法判断一个素数最多需要O(\sqrt(n))
的复杂度,判断n个就是O(n\sqrt{n})
埃式筛法
欲判断[2, n]
内的数的素性,从前往后一个一个扫描,若当前数未做合数标记,那么它就是质数,比如一开始就能判断2和3都是质数;每扫描到一个质数p,那么它的任何不大于n的倍数都是合数,就把2p, 3p, 4p,,,一直到n为止这些数都标记为质数。时间复杂度略大于O(n)
。
因为在标记的时候仅是在扫描到质数时才开始标记工作,若对于[1, n]
内每一个数都进行如上标记,那么时间复杂度为O(nlogn)
。即\sum_{i=1}^{n}n/i \approx nlogn
.
欧拉筛
线性处理素数的方法,利用唯一分解定理得到一个性质:每个合数总会有一个最小的质因数,利用这个最小的质因数来标记该合数,每个数只会被标记1次,时间复杂度为O(n)
。
步骤:同样是从前往后一个个扫描,若扫描到的数未被标记,它就是质数,并将该质数p存进质数数组prime里,用cnt来记录此时已经得到多少个素数,prime数组里的质数是从小到大排列好的。再扫描prime数组,对于那些小于p的
Miller-Rabin素性测试
米勒罗宾素性测试可以在较短的时间内判断出一个大整数的素性。比如现在想判断一个长度100位的整数是否为素数,使用上面的几种方法都不能在短时间内得到结果,因此很难得到一个确定的结果来判断该整数是否为素数。可以考虑对整数进行素性测试,具体需要用到下面两个定理。
费马小定理:若n为质数,则对于任意整数a,有a^{n-1}(\%n)=1
,但是当该式成立时,n不一定是质数;当a^{n-1}(\%n)
的结果不为1是,n一定是合数。可以以此来在一定程度上测试一个数的素性。(费马小定理推广自欧拉定理)
二次探测定理:若n为质数,则方程x^2(\%n)=1
的解只有1和n-1.对方程进行变形:x^2-1=an, (x+1)(x-1)=an
,n为素数所以没有其余的质因子,方程成立的情况只能是x=1或者x=n-1。这里的x都是经过对n取模后的值。
米勒罗宾素性测试步骤为:每一轮测试中,选取一个测试因子a,先计算a^{n-1}\%n
的值是否为1,不是1的话测试不通过,n一定为合数;否则继续使用二次探测定理进行测试,对n-1进行开方,若开方得到的值为n-1,测试通过,n可能为质数;若开方得到的值为1,那么可以继续开方;若得到了其它值,那么测试不通过,n一定是合数。
在代码实现中,步骤和上述是反着来的:先对n-1不断开方,即表示成n-1=2^{s}·d
的形式,d为奇数,s大于1。
然后先计算2^d\%n
是否为1或n-1,若是,则测试通过;否则,一定是在开方过程中有某一步模n出现了其它值,就开始对该值进行平方取模操作。若先得到n-1,则测试通过;若先得到1,则说明存在x使得x^2=1
的解不是1也不是n-1,那么测试不通过,n一定为合数。若已经平方过s次后还未退出上述循环,也就是说此时计算的值已经达到了a^{n-1}
,那么此时不论结果是1还是n-1,n都一定是合数。
因为计算过程中要用到高精度,时间复杂度为O((lgn)^3)
python代码如下:
def pmod(a, b, c):
if (a==0):
return 0
ans = 1
while b>0:
if (b&1):
ans = ans*a%c
b >>= 1
a = a*a%c
return ans
def check(a, n):
d = n-1
s = 0
while (d&1)==0:
d >>= 1
s+=1
t = pmod(a, d, n)
if t==1 or t==n-1:
return True
while (s>0):
s -= 1
if (t==n-1):
return True
if t==1:
return False
t = t*t%n
return False
def solve(n):
if (n<1000):
f = 0
for i in range(2, n):
if n%i==0:
f = 1
break
if f==0:
print("Yes")
else:
print("No")
return 0
for a in range(16350, 16351):
if False==check(a, n):
print("No")
return 0
print("Yes")
return 0
while True:
try:
s = input()
solve(int(s))
except EOFError:
break
Java代码,C++就先暂时放着吧...有时间整理一下大整数再写
import java.math.BigInteger;
import java.util.Scanner;
public class primeJudge{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
if ( false==isprime.primejudge(new BigInteger(scanner.nextLine())) ) System.out.println("No");
else System.out.println("Yes");
}
scanner.close();
}
};
class isprime {
public static boolean primejudge(BigInteger n) {
if (n.subtract(new BigInteger("1000000")).signum() <= 0 ) {
int tmp = Integer.valueOf(n.toString());
for (int i=2; i*i<=tmp; i++) if (tmp%i==0)
return false;
return true;
}
for (int a = 16350; a<=16360; a++) {
if (Miller_Rabin(n, new BigInteger(String.valueOf(a)))==false)
return false;
}
return true;
}
// 快速幂 a^b%m
private static BigInteger qpow(BigInteger a, BigInteger b, BigInteger m, BigInteger yi, BigInteger er) {
if (b.signum()==0) return new BigInteger("0");
BigInteger ans = new BigInteger("1");
while (b.signum()==1) {
if (b.mod(er).equals(yi)) ans = (ans.multiply(a)).mod(m);
b = b.divide(er);
a = (a.multiply(a)).mod(m);
}
return ans;
}
// 一次米勒罗宾测试
private static boolean Miller_Rabin(BigInteger n, BigInteger a) {
BigInteger d = new BigInteger("0");
BigInteger yi = new BigInteger("1");
BigInteger er = new BigInteger("2");
BigInteger tmp = n.subtract(yi);
d = n.subtract(yi);
int s = 0;
//233System.out.println(d.mod(er).toString());
while (d.mod(er).equals(yi)==false) {
s++;
d = d.divide(er);
}
BigInteger t = qpow(a, d, n, yi, er);
if (t.equals(yi) || t.equals(tmp)) return true;
while (s>0) {
s -= 1;
if (t.equals(tmp)) return true;
if (t.equals(yi)) return false;
t = t.multiply(t).mod(n);
}
return false;
}
};
// 大概20次米勒罗宾测试消耗1000ms
代码中我选取的测试因子a是从16350开始的连续几个数,选了几个数就是进行几轮测试,测试出错的改率为\frac{1}{2^{k}}
,k为测试次数。
我瞎选的这个数出错率还是挺低的
题目链接:
水题
若干测试数据,每行一个一百位以内的正整数,判断是否为素数。("Yes" "No")
数论一·Miller-Rabin质数测试
第一行给出测试数据个数,接下来每行一个long long范围内的数,测试是否为素数。
0 条评论