半素数

比100小的半素数有：

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95 （OEIS数列A001358）.

不是平方数的半素数被称为离散、特异或非平方半素数，包括：

6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... （OEIS数列A006881）

半素数是${\displaystyle k=2}$ 的${\displaystyle k}$ 次殆素数（有且仅有${\displaystyle k}$ 个素因数的数）。 但是有些数列将“半素数”解释为一种更加宽泛的数，即最多有两个素因数的数^[2]，包括：

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, ... （OEIS数列A037143）

除了自己本身外，半素数没有其他合数因数。^[3]例如，1、2、13及26是半素数26的因数，其中只有26是合数。

对于非平方半素数${\displaystyle n=pq}$ （${\displaystyle p\neq q}$ ），其欧拉函数的值${\displaystyle \varphi (n)}$ （小于或等于${\displaystyle n}$ 的正整数中与${\displaystyle n}$ 互质的数的数目）可以用简单的公式表达：

${\displaystyle \varphi (n)=(p-1)(q-1)=n-(p+q)+1.}$ 

这个公式是RSA加密算法半素数应用的重要部分。^[4]对于一个平方半素数，该公式又会简化为：^[4]

${\displaystyle \varphi (n)=p(p-1)=n-p.}$ 

半素数在密码学和数论中非常有用，最显著的例子的是RSA加密算法和随机数发生器等公开密钥加密应用。这些应用的基本原理是，计算两素数相乘结果（一个半素数）的过程简单，而反过来整数分解大半素数则比较困难。简单的来说，虽然35很容易就可以被分解成5×7，但是要想分解很大的半素数就不是那么容易了。RSA加密算法中有一个称为RSA-2048的半素数，有2,048位元，十进制有617位，RSA曾经公开悬赏200,000美元，给予成功将RSA-2048约数分解的人，迄2007年活动终止，未有人挑战成功领取悬赏。^[5]

1974年，阿雷西博信息通过无线电信号被发向星团。其由1679个二进制数字组成，这些数字的用意是让接收方将信息解析成位图图像。选择数字${\displaystyle 1679=23\cdot 73}$ 是因为其是一个半素数，只存在一种构成矩形图像的可能（up to 图像平面的旋转和反射）。^[6]

• 陈氏定理

• 埃里克·韦斯坦因. Semiprime. MathWorld. 
• 前10000个半素数（页面存档备份，存于互联网档案馆）