使用试除法，将37除以m = 2, 3, 4, 5, 6，没有一个数能整除37，因此37为素数。此一程序若能知道直至

的所有素数列表，因为试除法只检查m为素数的状况，所以会更有效率。例如，为检查37是否为素数，只有3个相除是必要的（m = 2, 3, 5），因为4与6为合数。

作为一个简单的方法，试除法在测试大整数时很快地会变得不切实际，因为可能的约数数量会随着n的增加而迅速增加。依据下文所述之素数定理，小于

的素数之数量约为

，因此使用试除法测试n是否为素数时，大约会需要用到这么多的数字。对n = 1020，此一数值约为4.5亿，对许多实际应用而言都太过庞大。

筛法

一个能给出某个数值以下的所有素数之算法，称之为素数筛法，可用于只使用素数的试除法内。最古老的一个例子为埃拉托斯特尼筛法（见上文），至今仍最常被使用。阿特金筛法为另外一例。在电脑出现之前，筛法曾被用来给出107以下的素数列表。

测试证明

现代测试一般的数字n是否为素数的方法可分成两个主要类型，随机（或“蒙特卡洛”）与确定性算法。确定性算法可肯定辨别一个数字是否为素数。例如，试除法即是个确定性算法，因为若正确执行，该方法总是可以辨别一个素数为素数，一个合数为合数。随机算法一般比较快，但无法完全证明一个数是否为素数。这类测试依靠部分随机的方法来测试一个给定的数字。例如，一测试在应用于素数时总是会通过，但在应用于合数时通过的概率为p。若重复这个测试n次，且每次都通过，则该数为合数的概率为1/(1-p)n，会随着测试次数呈指数下滑，因此可越来越确信（虽然总是无法完全确信）该数为素数。另一方面，若测试曾失败过，则可知该数为合数。

随机测试的一个特别简单的例子为费马素数判定法，使用到对任何整数a，np≡n (mod p)，其中p为素数的这个事实（费马小定理）。若想要测试一个数字b是否为素数，则可随机选择n来计算nb (mod b)的值。这个测试的缺点在于，有些合数（卡迈克尔数）即使不是素数，也会符合费马恒等式，因此这个测试无法辨别素数与卡迈克尔数，最小的三个卡迈克尔数为561，1105，1729。卡迈克尔数比素数还少上许多，所以这个测试在实际应用上还是有用的。费马素数判定法更强大的延伸方法，包括贝利-PSW、米勒-拉宾与Solovay-Strassen素数测试，都保证至少在应用于合数时，有部分时候会失败。

确定性算法不会将合数错误判定为素数。在实务上，最快的此类方法为椭圆曲线素数证明。其运算时间是透过实务分析出来的，不像最新的AKS素数测试，有已被严格证明出来的复杂度。确定性算法通常较随机算法来得慢，所以一般会先使用随机算法，再采用较费时的确定性算法。

下面表格列出一些素数测试。运算时间以被测试的数字n来表示，并对随机算法，以k表示其测试次数。此外，ε是指一任意小的正数，log是指一无特定基数的对数。大O符号表示，像是在椭圆曲线素数证明里，所需之运算时间最长为一常数（与n无关，但会与ε有关）乘于log5 ε(n)。

除了前述可应用于任何自然数n之上的测试外，一些更有效率的素数测试适用于特定数字之上。例如，卢卡斯素数测试需要知道n − 1的素因数，而卢卡斯-莱默素数测试则需要以n 1的素因数作为输入。例如，这些测试可应用在检查

n! ± 1 = 1 × 2 × 3 × ... × n ± 1

是否为一素数。此类形式的素数称之为阶乘素数。其他具p 1或p-1之类形式的素数还包括索菲·热尔曼素数（具2p 1形式的素数，其中p为素数）、素数阶乘素数、费马素数与梅森素数（具2p − 1形式的素数，其中p为素数）。卢卡斯-雷默素数测试对这类形式的数特别地快。这也是为何自电脑出现以来，最大已知素数总会是梅森素数的原因。

费马素数具下列形式

Fk = 22k 1,

其中，k为任意自然数。费马素数以皮埃尔·德·费马为名，他猜想此类数字Fk均为素数。费马认为Fk均为素数的理由为此串列的前5个数字（3、5、17、257及65537）为素数。不过，F5却为合数，且直至2015年发现的其他费马数字也全都是合数。一个正n边形可用尺规作图，当且仅当

n = 2i × m

其中，m为任意个不同费马素数之乘积，及i为任一自然数，包括0。

下列表格给出各种形式的最大已知素数。有些素数使用分散式计算找到。2009年，互联网梅森素数大搜索因为第一个发现具至少1,000万个数位的素数，而获得10万美元的奖金。电子前哨基金会亦为具至少1亿个数位及10亿个数位的素数分别提供15万美元及25万美元的奖金。

整数分解

给定一合数n，给出一个（或全部）素因数的工作称之为n的约数分解。椭圆曲线分解是一个依靠椭圆曲线上的运算来分解素因数的算法。

长期以来，数论，尤其是对素数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪。然而，此一观点在1970年代时遭到粉碎，当素数被公开宣布可以作为产生公钥加密算法的基础之时。素数现在也被用在杂凑表与伪乱数产生器里。

旋转机被设计成在每个转片上有不同数目的销，在每个转片上的销的数量都会是素数，亦或是会与其他转片上的销的数量互素。这有助于在重复所有的组合之前，让所有转片的可能组合都能出现过一次。

国际标准书号的最后一码为校验码，其算法使用到了11是个素数的这个事实。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。

在害虫的生物生长周期与*虫剂使用之间的关系上，*虫剂的素数次数的使用也得到了证明。实验表明，素数次数地使用*虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

素数运算

“模运算”使用下列数字修改了一般的运算