判定素数的方法有哪些?它们的时间复杂度分别是多少?(越详细越好,有高分奖励)

 我来答
LIUZH1201
2011-12-27 · TA获得超过1063个赞
知道答主
回答量:105
采纳率:0%
帮助的人:36.3万
展开全部
几种简单的判断素数的方法
素数还有很多东西需要学,先整理三种最简单的判断素数的方法,以后再深究补充。

判断n是否为素数

1、最简单的方法
用n除以2-sqrt(n),有一个能除尽就不是素数,否则是素数。
时间复杂度:O(sqrt(n))

2、素数判断法:
这种方法是对上面方法的改进,上面方法是对2-sqrt(n)之间的数进行判断是否能除尽,而因为有如下算术基本定理,可以减少判断量。
算术基本定理:又称为素数的唯一分解定理,即:每个大于1的自然数均可写为素数的积,而且这些素因子按大小排列之后,写法仅有一种方式。例如:6936 = 2^3×3×17^2,1200 = 2^4×3×5^2。
由算术基本定理知,任何合数都可分解为一些素数的乘积,所以判断一个数能不能被2-sqrt(n)之间的素数整除即可。但是必须知道2-sqrt(n)之间的所有素数。

3、筛选法
这种方法可以找出一定范围内的所有的素数。
思路是,要求10000以内的所有素数,把1-10000这些数都列出来,1不是素数,划掉;2是素数,所有2的倍数都不是素数,划掉;取出下一个幸存的数,划掉它的所有倍数;直到所有幸存的数的倍数都被坏掉为止。

要找出10000以为的所有的素数,则需要一个大小为10000的数组,将其所有元素设置为未标记
首先把1设置为标记,从2开始,标记所有是它倍数的数,然后对下一个没有标记的数进行标记它的倍数。
当标记完成后,所有未标记的数即为素数。
这种算法需要O(n)的空间,不要偶数,可以节省一半的存储空间,标记需要O(n^2/logn)(我写的,不知道对不对),判断是否是素数只需要O(1)的时间。

贴一下程序代码:

/*
2009.5.12 by HK
*/
#include <stdio.h>
#include <math.h>
#include <string.h>

int a[10000];

//100以内的素数
int prime100[] =
{
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
};

/************************************************************************/
/* 第一种方法:最简单的方法 */
/************************************************************************/

int is_prime1(int n)
{
if(n % 2 == 0)
return 0;

for(int i=3;i<=sqrt((double)n);i+=2)
if(n % i == 0)
return 0;

return 1;
}

/************************************************************************/
/* 第二种方法:素数判断法 */
/* 若判断10000以内的数,需要知道100以内的所有素数 */
/************************************************************************/

int is_prime2(int n)
{
int i;
for(i=0;i<25;i++)
if(n % prime100[i] == 0)
return 0;
return 1;
}

/************************************************************************/
/* 第三种方法:筛选法,打素数表,然后判断 */
/************************************************************************/

//筛选,a[i]=0,i为素数
void create_table()
{
int i, tmp;
memset(a, 0, sizeof(a));
a[0] = 1;
a[1] = 1;
for(i=2;i<10000;i++)
{
if(!a[i])
{
tmp = i*2;;
while(tmp < 10000)
{
a[tmp] = 1;
tmp += i;
}
}
}
}

int is_prime3(int n)
{
return !a[n];
}

int main()
{
int num, res;
create_table();
printf("Input the num:");
scanf("%d", &num);
res = is_prime3(num);
if(res)
printf("%d is a prime\n", num);
else
printf("%d is not a prime\n", num);
return 0;
qweytr_1
2011-12-29 · 超过46用户采纳过TA的回答
知道小有建树答主
回答量:91
采纳率:0%
帮助的人:78.4万
展开全部
据说AKS算法特快,不过我没看懂,没办法直接解释
还可以对数进行素性测试(通过不一定是,但通不过一定不是):
原理是Femart小定理的逆命题(可惜在少数情况下不成立)
Femart小定理:若p是素数,则p整除[(a^p)-a]
由此可以写出判定(一般用前5个质数,这样至少在longint精度内没有反例)
这样的时间复杂度可以在logn的范围内

程序:
(0)计算a^b(mod c)
思路:先令ans=1,用二进制将b展开,
然后不断地重复:
若b的最末以为二进制数为1,ans=ans*a
对a赋值(a*a) mod p,
将b的二进制最后一位去掉
直到b=0

(1)
(直接用pascal写下吧:)
分别令p取2,3,5,7,11,13
计算a^(p-1)(mod c)只需看看有没有输出不是1的,若没有这个数在longint范围内一定是质数)

至于更广的范围,可以查伪素数表。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
352901753
2011-12-28 · TA获得超过140个赞
知道答主
回答量:584
采纳率:100%
帮助的人:158万
展开全部
筛选。。。。越大,越复杂,越往后,越接近2的N次方初一某个数,甚至乘
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
100942649
2011-12-29
知道答主
回答量:3
采纳率:0%
帮助的人:4980
展开全部
gndgvnj
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
229101523
2011-12-29
知道答主
回答量:4
采纳率:0%
帮助的人:3.3万
展开全部
srt6r56 7u
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 2条折叠回答
收起 更多回答(3)
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式