概率性算法的缺陷就是在最坏情况下的耗时是无穷。

但是概率性算法的好处就是平均时间复杂度最低。

概率性算法有：费马检测，米勒罗宾算法，Baillie–PSW

确定性算法有：试除法，改进后的试除法，ECPP，APR-CL（Adleman–Pomerance–Rumely-Cohen-Lenstra），以及AKS。

而AKS我想就是题主需要的答案了

AKS最关键的重要性在于它是第一个被发表的一般的、多项式的、确定性的和无仰赖的素数判定算法。先前的算法至多达到了其中三点，但从未达到全部四个。AKS算法可以被用于检测任何一般的给定数字是否为素数。很多已知的高速判定算法只适用于满足特定条件的素数。例如，卢卡斯-莱默检验法仅对梅森素数适用，而Pépin测试仅对费马数适用。
算法的最长运行时间可以被表为一个目标数字长度的多项式。ECPP和APR能够判断一个给定数字是否为素数，但无法对所有输入给出多项式时间范围。
算法可以确定性地判断一个给定数字是否为素数。随机测试算法，例如米勒-拉宾检验和Baillie–PSW，可以在多项式时间内对给定数字进行校验，但只能给出概率性的结果。
AKS算法并未“仰赖”任何未证明猜想。一个反例是确定性米勒检验：该算法可以在多项式时间内对所有输入给出确定性结果，但其正确性却基于尚未被证明的广义黎曼猜想。【引用自百度百科】

AKS算法的时间复杂度是，后来被改进到。