质数判定
- 格式：doc
- 大小：43.00 KB
- 文档页数：3
质数判定
质数又称素数。
指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
换句话说，只有两个正因数（1和自己）的自然数即为素数。
比1大但不是素数的数称为合数。
1和0既非素数也非合数。
合数是由若干个质数相乘而得到的。
所以，质数是合数的基础，没有质数就没有合数。
这也说明了前面所提到的质数在数论中有着重要地位。
历史上曾将1也包含在质数之内，但后来为了算术基本定理，最终1被数学家排除在质数之外，而从高等代数的角度来看，1是乘法单位元，也不能算在质数之内，并且，所有的合数都可由若干个质数相乘而得到。
一、线性法判定质数
1、主要思想
依次将i 取2至n/2的所有正整数，如果n 能被i 整除，则n 为合数；如果n 不能被所有的i 所整除，则n 为质数。
2、时间复杂度 在最不利的情况下，线性法的时间复杂度为)2
(n O 。
二、抛物线法判定质数
1、主要思想
在平面直角坐标系上画出抛物线y = x 2的图像，然后标出抛物线上的所有格点（两坐标均为整数的点）。
其中，只有点(0, 0)正好在y 轴上，其余的点要么在y 轴左侧，要么在y 轴右侧。
把y 轴左侧除了(-1, 1)以外的所有格点与y 轴右侧除了(1, 1)以外的所有格点相连，这些连线将自动避开y 轴上纵坐标为质数的点。
连接足够多的线条之后，质数就逐渐露了出来。
2、原理分析
任取实数a 、b ，则点(-a, a 2)和点(b, b 2)的连线必定经过点(0, a·b )，这可以通过计算斜率的方法得到验证。
这个颇具创意的质数筛选法叫做visual sieve ，它是由Yuri Matiyasevich 和Boris Stechkin 提出的。
由于抛物线是左右对称的，因此格点间的连线也只需作半边，即将y 轴左侧的一个格点(-a, a 2)（a 2<n ）与(0, n )相连，连线方程为
n x a
a n y +-=2
连线与抛物线y = x 2在抛物线右侧的交点横坐标为
a
n a a n a n x 24)()(2222+-+-= 如果该交点是抛物线右边除(1, 1)以外的格点之一，则n 是合数，否则n 为质数。
3、时间复杂度 根据算法原理，可见在最不利的情况下抛物线法的时间复杂度为)(n O 。
参考资料
[1] /view/10626.htm
[2] /699142734/note/787259544?&ref=minifeed&sfet=2003&fin=4&ff_id= 233134409&feed=user_blogshare&statID=page_699142734_2&level=2
MATLAB 程序
1、质数判定
function R=PrimeNumber(n)
%==================================================================== %判断n 是否为质数：若是，返回1；若不是，返回0；若输入为非整数，返回-1
%==================================================================== if ceil(n)~=n
R=-1;
else
if n<=0
R=0;
else
R=1;
for a=2:ceil(sqrt(n))
x=((n-a*a)+sqrt((n-a*a)^2+4*a*a*n))/(2*a);
if ceil(x)==x & n~=2 %如果x 是整数
R=0;
break;
end;
end;
end;
end;
2、分解质因数
function [Z,T]=PrimeFactors(n)
%===================================================================
%分解质因数：返回值Z为输入数的质因数；返回值T为对应位置质因数的次数。
%仅对整数求解，输入非整数时返回值为空。
%需调用质数判定函数PrimeNumber(a)。
%==================================================================== %初始化
P=[]; %n可能的质因数
Z=[]; %记录质因数
T=[]; %记录对应质因数的次数
if n<0
Z(1)=-1;
T(1)=1;
n=abs(n);
end;
if n==1
Z(length(Z)+1)=1;
T(length(T)+1)=1;
end;
if PrimeNumber(n)==1
Z(length(Z)+1)=n;
T(length(T)+1)=1;
end;
if ceil(n)==n & n~=1 & PrimeNumber(n)~=1
%生成质数表：列出不大于n/2的所有质数
for a=2:floor(n/2)
if PrimeNumber(a)==1
P(length(P)+1)=a;
end;
end;
for x=1:length(P)
if ceil(n/P(x))==n/P(x)
Z(length(Z)+1)=P(x);
T(length(T)+1)=0;
end;
while ceil(n/P(x))==n/P(x)
T(length(T))=T(length(T))+1;
n=n/P(x);
end;
end;
end;。
