一句话结论
公民身份号码（仅考虑 18 位公民身份号码）有可能是素数，任意给定一个随机、有效的公民身份证号码，此号码为素数的概率理论上为 2.20%，实际验证结果约为 2.25%。
身份证号码的规律
这篇回答下面已经简要介绍了中华人民共和国公民身份号码的规定，这里不妨再详细展开介绍一下。
中华人民共和国国家标准《GB11643-1999 公民身份号码》第 5 节：号码的结构和表示形式中有如下规定：
5.1 号码的结构
公民身份号码是特征组合码，由十七位数字本体码和一位数字校验码组成。排列顺序从左至右依次为：六位数字地址码，八位数字出生日期码，三位数字顺序码和一位数字校验码。
这里我们仅考虑第二代身份证的身份号码，即上述 18 位身份号码。
5.1.1 地址码
表示编码对象常住户口所在县（市、旗、区）的行政区域代码，按 GB/T 2260 的规定执行。
这个 GB/T 2260 标准有点麻烦。
根据“标准下载库”的描述，中华人民共和国国家推荐标准《GB/T 2260 中华人民共和国行政区划代码》于 1980 年 12 月首次发布，1982 年、1984 年、1986 年、1988 年、1991 年、1995 年、1999 年、2002 年、2007 年先后进行了九次修订。当前实施的版本为《GB/T 2260-2007/XG1-2016》，也就是 2007 年修订的版本，于 2017 年 01 月 01 日起正式实施。
GB/T2260-2007 与 GB/T2260-2002 相比，主要变化表现在对应于行政区划变更的代码修订和区划名称变化，合计为：撤销数字码 238 个，新赋数字码 255 个；撤销字母码 104 个，新赋字母码 103 个；区划名称变化 182 处。这么看来，不同时间段还应该使用不同版本的国家推荐标准了。
这还不算完，打开中华人民共和国民政部网站，会发现民政部隔三差五就会调整一下地址码。2019 年 12 月 24 日就发布了一次最新版本的《中华人民共和国县以上行政区划代码》。
幸好，我们可以找到很多已经用代码实现完毕的地址码库。https://github.com/cn/GB2260就是这样一个好用的地址码库，支持多种语言，童叟无欺！不过，为了方便起见，我直接到 CSDN 上找了一个看似能用的《2019 年全国省市县行政区划编码表》：
2019 年全国省市县行政区划编码表.xlsx- 互联网文档类资源 -CSDN 下载
这个 Excel 文件里面总共包含了 2884 个地址码。
5.1.2 出生日期码
表示编码对象出生的年、月、日，按 GB/T 7408 的规定执行。年、月、日代码之间不用分隔符。
例：某人出生日期为 1966 年 10 月 26 日，其出生日期码为 19661026。
这个比较简单。
5.1.3 顺序码
表示在同一地址码所标识的区域范围内，对同年、同月、同日出生的人编订的顺序号，顺序码的奇数分配给男性，偶数分配给女性。
这个看起来也比较...别忙，这里有一个很坑的点。
如果你是 1999 年之前出生的中华人民共和国公民，那你的户口本上最开始登记的身份证号码不是 18 位的，而是 15 位的，也就是少了出生日期码的前两位，以及最后一位校验码。少了出生日期码的前两位有一个很麻烦的问题：一个 1899 年出生的百岁老人和一个 1999 年出生的儿童，其出生日期码的前两位均是 99，如果顺序码又一样，很可能这两个人都会具有相同的公民身份号码。为了解决这个问题，第一代身份证首次赋码时，将 990~999 留下备用，专门赋给百岁老人。不过，随着第二代身份证上公民身份号码升级为 18 位，上述问题已经不存在了，因此现在 990~999 已经不再作为百岁老人的备用顺序码。这方面具体可参考知友 @ls Shaw 的答案：
5.1.4 校验码
校验码采用 ISO 7064:1983,MOD 11-2 校验码系统。
这个解释起来有点复杂，我们直接上计算公式就好了。CSDN 上的网友Stone.小小的太阳的文章《Java 代码实现身份证合法性校验（全国所有地方）》中代码的注释很好地描述了校验码的计算和使用方法：
第十八位数字(校验码)的计算方法为：
1. 将前面的身份证号码 17 位数分别乘以不同的系数。从第一位到第十七位的系数分别为：7、9、10、5、8、4、2、1、6、3、7、9、10、5、8、4、2。
2. 将这 17 位数字和系数相乘的结果相加。
3. 用加出来和除以 11，看余数是多少。
4. 余数只可能有 0、1、2、3、4、5、6、7、8、9、10 这 11 个数字，其分别对应的最后一位身份证的号码为 1、0、X、9、8、7、6、5、4、3、2。
有了上述信息，理论上我们就可以生成所有可能的公民身份号码了。
素性检测
如何检测一个公民身份号码是否为素数呢？检测一个数是否为素数的算法称为”素性检测“。而当前比较易用的素性检测算法为 Miller-Rabin 素性检测法。Java 编程语言 BigInteger 类中内置的素性检测算法即为 Miller-Rabin 素性检测法，实际上，BigInteger 类中判断给定的 BigInteger 是否为素数的方法 probablePrime 中调用了一个私有方法 passesMillerRabin，其注释为：
Returns true iff this BigInteger passes the specified number of Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS 186-2).
Miller-Rabin 素性检测法并不是 Miller 和 Rabin 一起提出的。最开始，卡耐基梅隆大学的 Gary Lee Miller 首先提出的是一个基于广义黎曼猜想的确定性素性检测算法，但由于广义黎曼猜想并没有被证明，因此这一算法是否真的可靠尚不可知。随后，以色列耶路撒浪希伯来大学的 Michael O. Rabin 对此算法进行了修改，提出了不依赖于广义李曼猜想的随机素性检测算法。
Miller-Rabin 素性检测法只能以非常非常大的概率判定一个数是否为素数，但不能 100%判定。使用此算法时需要设置一个判定失败的概率，我们设置的概率为
。
如果想了解更多有关素性检测的知识，可以阅读 Matrix67 的文章：
http://www.matrix67.com/blog/archives/234
知友 @JoJo 王颀 的答案也非常值得一读：
初步估算结果
有了公民身份号码生成方法，也有了素性检测算法，理论上我们就可以生成所有可能的身份证号码，并把素数的公民身份号码挑出来了。不过在此之前，我们可以初步估计一下有多大比例的公民身份号码可能为素数。
知友 @xiaomm8341 已经指出：
根据素数定理，18 位整数是素数的概率是：
再加上末尾可能是 X，所以需要乘以 10/11，因此是素数的可能性平均是
实际上，素数定理描述了素数在自然数中分布的近似分布情况。素数定理指出，给出随着数字的增大，素数的密度逐渐降低。令
为不大于
的素数个数，则有：
。
因此根据素数定理，给定任意一个长度为 18 位的整数（范围从 0 到 999999999999999999），此整数为素数的概率近似为
。由于末尾为 X 的公民身份号码一定不是素数，故可得到一个初步的占比估计值
。
实际验证结果
我们遍历 2000 年 01 月 01 日至 2000 年 01 月 31 日这一个月内所有可能的公民身份号码，但有下述约束条件：
- 不考虑百岁老人情况（即 3 位随机码可以为 990~999）；
- 不考虑出生分布情况（大部分城市一天出生的人数远小于 999）；
- 仅考虑 CSDN 上《2019 年全国省市县行政区划编码表》中包含的 2884 个地址码；
因此，总共可能的公民身份号码个数为
。
把所有有
的概率为素数的公民身份号码逐行写在一个文件中，这个文件竟然有 38.2MB 这么大：
经过验证，这 89404000 个公民身份号码中有 2012378 公民身份号码有
的概率为素数，占比约为 2.25%，看来素数定理还是很准的嘛~
总之，公民身份号码当然有可能是素数，而且概率不低。
