TOP榜写作榜手机小说

最近更新新书入库全部小说

迷你书窝 >> 数学心 >> 第141章 米勒拉宾素性测试

第141章 米勒拉宾素性测试

对于一个数n,如果想要判断它是否为素数,常规的方法为试除法。即,让n依次除以2到sqrt(n)以内的整数。如果有出现除尽的情况,则为合数。

该方法的时间复杂度为O(sqrt(n))在面对n为长整型的时候有可能超出时间要求。因此普遍采用米勒拉宾算法进行素性判定。

在此之前介绍一种伪素数判定方法——小费马定理。

但没有米勒拉宾素性测试快。

米勒拉宾素性测试是:

判断一个数p是否为素数

p首先得为大于等于2的正整数才有可能为素数,

首先判奇偶,若为偶数只有2为素数,

若为奇数(这里可以考虑去掉 3甚至5的倍数),则先求出d。

对于每一个底a,让d不断乘以2直到为(p-1)/2,

在此过程中(包括原本的d与d=(p-1)/2时的情况),

设t为 a的d次方模p的余数,

(1)当t=-1时跳出,声明p有可能为素数

(2)当t=1时,若d为奇数,跳出声明p有可能为素数,否则跳出声明p必为合数

(3)当d=(p-1)/2时跳出,声明p必为合数。

喜欢数学心请大家收藏:(www.mnowo.com)数学心迷你书窝更新速度全网最快。

数学心最新章节 - 数学心全文阅读 - 数学心txt下载 - 蔡泽禹的全部小说 - 数学心 迷你书窝

猜你喜欢: 捡个杀手做老婆娱乐韩娱超品相师重生1977年从知青开始女总裁的顶级高手不良之谁与争锋我的卡牌无限强化都市之修仙归来地产之王第一赘婿时尚大佬最强神眼全职狂少签到演员请就位农民小神医超级医生空速星痕这个心理学家很诡异全知全能者极品透视
完本推荐: 捡个杀手做老婆全文阅读都市最强特种兵全文阅读校花之贴身高手全文阅读极品全能学生全文阅读我的极品女老师全文阅读农民小神医全文阅读大小姐的贴身护卫全文阅读都市之修仙归来全文阅读我的绝色美女房客全文阅读女总裁的顶级高手全文阅读终极教官全文阅读重生之全能巨星全文阅读都市之活了几十亿年全文阅读第一赘婿全文阅读重生之杀戮纵横全文阅读一代天骄全文阅读捡宝王全文阅读神级奶爸全文阅读修仙归来在校园全文阅读桃运神戒全文阅读
同类新书: 医生:从心动开始文娱从高考满分作文开始智脑入侵从女团感谢祭开始制霸听说人皇又又又被赶出家门了何雨柱的全新生活文娱:我真不想当顶流重生为猫,混迹女生合租屋放弃留学,我打造了世界第一名校灾难来临:我的天赋是气人人生操盘开局从教idol养生开始冲呀,90我成了神话禁忌从姐姐开始的娱乐这个作者老想安排我神豪爱看直播神豪的俗人生活挽歌前行神豪超忐忑

数学心最新章节手机版 - 数学心全文阅读手机版 - 数学心txt下载手机版 - 蔡泽禹的全部小说 - 数学心 迷你书窝移动版 - 迷你书窝手机站