素数是公共密钥密码学（Public Key Cryptography, PKC）的基础。本文不深入探讨PKC，而是讨论素数如何被使用。例如，两个素数7和13的乘积很容易计算，结果是91。但如果有一个数91，想要找到一对素数，其乘积为91，这将更加困难，尽管最终可以找到。如果给定的数是一个128位的数字，那么快速找到它的因子则更加困难。这种“更难分解”的素数问题被用作PKC的基础。
暴力法是找到素数的最简单方法。要确定一个数是否为素数，需要将该数除以奇数，并检查余数，从3开始直到奇数的平方小于正在检查的数。如果没有余数，则该数不是素数；否则，它是素数。以下是检查素数的代码片段。totalCount初始化为1，因为2是素数，在代码中被忽略。
int totalCount = 1;
bool isPrime = true;
for (long i = 3; i < topCandidate; i += 2)
{
for (int j = 3; j * j <= i; j += 2)
{
if ((i % j) == 0) { isPrime = false; break; }
}
if (isPrime) { totalCount++; }
else isPrime = true;
}
return totalCount;
暴力法是最简单的方法，但它的效率较低，特别是对于大数。
埃拉托斯特尼筛法是一种古老的算法，用于找到素数，也是第一个被编写的高效算法。算法本身相当简单。例如，要找到小于10的素数，创建一个长度为10的布尔数组，所有值都为true。从2开始，将2的倍数在数组中设置为false。这个过程一直持续到该数的倍数小于10。最后，所有值为true的索引（除了索引1）都被认为是素数。
int totalCount = 0;
BitArray myBA1 = new BitArray(topCandidate + 1);
myBA1.SetAll(true);
myBA1[0] = myBA1[1] = false;
int thisFactor = 2;
int lastSquare = 0;
int thisSquare = 0;
while (thisFactor * thisFactor <= topCandidate)
{
int mark = thisFactor + thisFactor;
while (mark <= topCandidate)
{
myBA1[mark] = false;
mark += thisFactor;
}
thisSquare = thisFactor * thisFactor;
for (; lastSquare < thisSquare; lastSquare++)
{
if (myBA1[lastSquare]) totalCount++;
}
thisFactor++;
while (!myBA1[thisFactor]) { thisFactor++; }
}
for (; lastSquare <= topCandidate; lastSquare++)
{
if (myBA1[lastSquare]) { totalCount++; }
}
埃拉托斯特尼筛法比暴力法更高效，但受到内存限制，就像其他素数计算算法一样。
桑德拉姆筛法比埃拉托斯特尼筛法更高效。它使用与埃拉托斯特尼筛法类似的筛法原理，但不包括偶数。它在筛子（布尔数组）中划掉任何形式为i+j+2ij的数字，其中i >= 1且小于n/2，j >= i且小于n，n是想要找到所有素数的数字。最后，筛子中值为true的索引乘以2并加1，得到素数。
int maxVal = 0;
int denominator = 0;
for (int i = 1; i < k; i++)
{
denominator = (i << 1) + 1;
maxVal = (k - i) / denominator;
for (int j = i; j <= maxVal; j++)
{
myBA1[i + j * denominator] = false;
}
}
int prime = 0;
for (int i = 1; i < k; i++)
{
if (myBA1[i])
{
totalCount++;
prime = (i << 1) + 1;
}
}
桑德拉姆筛法的性能优于埃拉托斯特尼筛法，但内存限制是埃拉托斯特尼筛法的一半。
阿特金筛法是对埃拉托斯特尼筛法的改进。它不是通过循环遍历所有数字来确定它们是否为素数，而是依赖于二次方程和模60来找到素数/非素数的模式，并在布尔数组中标记它们。
int totalCount = 0;
BitArray isPrime = new BitArray(topCandidate + 1);
int squareRoot = (int)Math.Sqrt(topCandidate);
int xSquare = 1, xStepsize = 3;
int ySquare = 1, yStepsize = 3;
int computedVal = 0;
for (int x = 1; x <= squareRoot; x++)
{
ySquare = 1;
yStepsize = 3;
for (int y = 1; y <= squareRoot; y++)
{
computedVal = (xSquare << 2) + ySquare;
if ((computedVal <= topCandidate) && (computedVal % 12 == 1 || computedVal % 12 == 5))
isPrime[computedVal] = !isPrime[computedVal];
computedVal -= xSquare;
if ((computedVal <= topCandidate) && (computedVal % 12 == 7))
isPrime[computedVal] = !isPrime[computedVal];
if (x > y)
{
computedVal -= ySquare << 1;
if ((computedVal <= topCandidate) && (computedVal % 12 == 11))
isPrime[computedVal] = !isPrime[computedVal];
}
ySquare += yStepsize;
yStepsize += 2;
}
xSquare += xStepsize;
xStepsize += 2;
}
for (int n = 5; n <= squareRoot; n++)
{
if (isPrime[n] == true)
{
int k = n * n;
for (int z = k; z <= topCandidate; z += k)
isPrime[z] = false;
}
}
for (int i = 1; i < topCandidate; i++)
{
if (isPrime[i]) totalCount++;
}
return (totalCount + 2);