求二进制表示中含32个置位比特位的最小素数

首先直接给答案：满足条件的最小素数是8581545983。下面我用普通人能看懂的逻辑一步步拆解怎么找到它：

核心问题拆解 #

我们要找的是：二进制里恰好有32个1，同时是素数的最小数。先明确两个关键点：

• 二进制里有32个1的数，要么是32位全1（只有一个数：2^32 - 1 = 4294967295），要么是更高位的数（比如33位）里恰好有一位是0、其余32位是1。
• 要找最小的，那肯定先从位数最少的候选开始检查，不行再找更高位里最小的候选。

第一步：检查32位唯一候选 #

32位里只有4294967295这一个数有32个1，但它是合数——分解一下，它等于3×5×17×257×65537，全都是费马素数，所以直接排除。

第二步：检查33位的候选 #

33位里有32个1的数，其实就是33位全1的数（2^33 - 1 = 8589934591）减去某个2^k（k从0到32），也就是(2^33 -1) - 2^k。要找最小的候选，就得让减去的2^k尽可能大（因为减的数越大，结果越小），所以我们从k=32开始往下逐个检查：

• k=32：结果就是4294967295，已经排除；
• k=31：结果是3×2^31 -1 = 6442450943，经检验是合数；
• k=30：结果是7×2^30 -1 = 7340031999，各位数字加起来是45，能被3整除，肯定是合数；
• k=29：结果是8053063679，合数；
• k=28：结果是8321499135，末尾是5，能被5整除，合数；
• k=27：结果是8455716863，合数；
• k=26：结果是8522825727，合数；
• k=25：结果是8556380159，合数；
• k=24：结果是8573157375，末尾是5，合数；
• k=23：结果是1023×2^23 -1 = 8581545983，经检验这个数是素数！

这就是我们要找的最小的那个，因为它是33位候选里第一个（也是最小的）素数，而比它小的候选要么是32位的合数，要么是33位里更小的合数。

内容的提问来源于stack exchange，提问作者Glenn Slayden