有人做過這樣的驗算：1^2+1+41=43,2^2+2+41=47,3^2+3+41=53……于是就可以有這樣一個公式：設一正數為n，則n^2+n+41的值一定是一個質數。這個式子一直到n=39時，都是成立的。但n=40時，其式子就不成立了，因為40^2+40+41=1681=41*41。
研究發現質數除2以外都是奇數，而奇數除了【奇數*奇數】(或再加“*奇數”）都是質數。那么用計算機先把【奇數*奇數】(或再加“*奇數”）（比如9，15，21，25，27，33，35，39……）都求出來，再找奇數中上面沒提到的那些數，那些數就是素數。
有近似公式： x 以內質數個數約等于 x / ln(x) .ln是自然對數的意思。準確的質數公式尚未給出。10 以內共 4 個質數。100 以內共 25 個質數。
古老的篩法：可快速求出100000000以內的所有素數。篩法，是求不超過自然數N（N＞1）的所有質數的一種方法。據說是古希臘的埃拉托斯特尼（Eratosthenes，約公元前274～194年）發明的，又稱埃拉托斯特尼篩子。具體做法是：先把N個自然數按次序排列起來。1不是質數，也不是合數，要劃去。第二個數2是質數留下來，而把2后面所有能被2整除的數都劃去。2后面第一個沒劃去的數是3，把3留下，再把3后面所有能被3整除的數都劃去。3后面第一個沒劃去的數是5，把5留下，再把5后面所有能被5整除的數都劃去。這樣一直做下去，就會把不超過N的全部合數都篩掉，留下的就是不超過N的全部質數。
素數判斷法：考慮到這么一個現實：任何一個合數都可以表現為適當個素數的乘積的形式，所以我們只用素數去除要判斷的數即可，比如要判斷100以內的素數，只用10以內的2，3，5，7就夠了，10000以內的數用100以內的素數判斷足以。
Rabin-Miller算法：首先我們必須保證n 是個奇數，那么我們就可以把n 表示為 n = (2^r)*s+1,注意s 也必須是一個奇數。然后我們就要選擇一個隨機的整數a (1<=a<=n-1)，接下來我們就是要判斷 a^s=1 (mod n) 或a^((2^j)*s)= -1（mod n）(0<=j如果任意一式成立，我們就說n通過了測試，但是有可能不是素數也能通過測試。所以我們通常要做多次這樣的測試，以確保我們得到的是一個素數。（DDS的標準是要經過50次測試）采用Rabin- Miller算法進行驗算的方法：
0、對于需要驗證的數n，先計算出m、j，使得n=1+m*2^j，其中m是正奇數，j是非負整數
1、隨機取一個b，2<=b<n
2、計算v=b^m mod n
3、如果v==1，通過測試，返回
4、令i=1
5、如果v=n-1，通過測試，返回
6、如果i==j，非素數，結束
7、v=v^2 mod n，i=i+1
8、循環到5