抽象代码：一个"O(1)"的质数判断器

先看运行效果。一个判断质数的程序，输入 7：

1
2
3

7 → 7 is a Prime
100 → 100 isn't a Prime
254 → 254 isn't a Prime

响应快得惊人，因为它一次除法都没做——不是算法好，是它根本不判断。它是一份”背好答案”的程序：把 1 到 255 每个数是不是质数，直接写成 1029 行 if-else。而这个程序的作者，是另一个程序。

生成器一号：把判断展开成 if-else

生成器的思路是时间换空间再换时间：生成的时候用普通试除法判断一次质数，然后把结果硬编码进一个新程序：

for (int i = 2; i < num; i++)
{
    char temp[50];
    sprintf(temp, "    else if(num == %d)\n", i);
    fprintf(fp, temp);

    fprintf(fp, "    {\n");
    if(isPrime(i))
    {
        sprintf(temp, "        printf(\"%d is a Prime\");\n", i);
    }
    else
    {
        sprintf(temp, "        printf(\"%d isn't a Prime\");\n", i);
    }
    fprintf(fp, temp);
    fprintf(fp, "    }\n");
}

isPrime(i) 只在生成阶段跑一遍，产出的 example.c 里只剩下 else if(num == 7) { printf("7 is a Prime"); } 这样的死答案。运行生成出来的程序，任何判断都不存在，查表即答。

真机验证这份 1029 行的产物（文件夹里现成的），输入 7、100、254，全部秒答正确：

1
2
3

7 → 7 is a Prime
100 → 100 isn't a Prime
254 → 254 isn't a Prime

不过它有个诚实的边界：只认 1 到 255。输入 256？if-else 链兜不住，程序沉默地什么都不输出——答案没背到那一页。

生成产物：example.c 完整代码

生成器当年吐出来的 example.c 全文如下（1029 行，一字未改）。全部智慧就是一根 if-else 链——顺便体验一下 253 个 else if 的视觉冲击。它接受一个整数输入，查到答案就报，查不到（大于 255）就保持沉默：

example.c

#include <stdio.h>

int main()
{
    int num;
    scanf("%d", &num);

    if(num == 1)
    {
        printf("1 isn't a Prime");
    }
    else if(num == 2)
    {
        printf("2 is a Prime");
    }
    else if(num == 3)
    {
        printf("3 is a Prime");
    }
    else if(num == 4)
    {
        printf("4 isn't a Prime");
    }
    else if(num == 5)
    {
        printf("5 is a Prime");
    }
    else if(num == 6)
    {
        printf("6 isn't a Prime");
    }
    else if(num == 7)
    {
        printf("7 is a Prime");
    }
    else if(num == 8)
    {
        printf("8 isn't a Prime");
    }
    else if(num == 9)
    {
        printf("9 isn't a Prime");
    }
    else if(num == 10)
    {
        printf("10 isn't a Prime");
    }
    else if(num == 11)
    {
        printf("11 is a Prime");
    }
    else if(num == 12)
    {
        printf("12 isn't a Prime");
    }
    else if(num == 13)
    {
        printf("13 is a Prime");
    }
    else if(num == 14)
    {
        printf("14 isn't a Prime");
    }
    else if(num == 15)
    {
        printf("15 isn't a Prime");
    }
    else if(num == 16)
    {
        printf("16 isn't a Prime");
    }
    else if(num == 17)
    {
        printf("17 is a Prime");
    }
    else if(num == 18)
    {
        printf("18 isn't a Prime");
    }
    else if(num == 19)
    {
        printf("19 is a Prime");
    }
    else if(num == 20)
    {
        printf("20 isn't a Prime");
    }
    else if(num == 21)
    {
        printf("21 isn't a Prime");
    }
    else if(num == 22)
    {
        printf("22 isn't a Prime");
    }
    else if(num == 23)
    {
        printf("23 is a Prime");
    }
    else if(num == 24)
    {
        printf("24 isn't a Prime");
    }
    else if(num == 25)
    {
        printf("25 isn't a Prime");
    }
    else if(num == 26)
    {
        printf("26 isn't a Prime");
    }
    else if(num == 27)
    {
        printf("27 isn't a Prime");
    }
    else if(num == 28)
    {
        printf("28 isn't a Prime");
    }
    else if(num == 29)
    {
        printf("29 is a Prime");
    }
    else if(num == 30)
    {
        printf("30 isn't a Prime");
    }
    else if(num == 31)
    {
        printf("31 is a Prime");
    }
    else if(num == 32)
    {
        printf("32 isn't a Prime");
    }
    else if(num == 33)
    {
        printf("33 isn't a Prime");
    }
    else if(num == 34)
    {
        printf("34 isn't a Prime");
    }
    else if(num == 35)
    {
        printf("35 isn't a Prime");
    }
    else if(num == 36)
    {
        printf("36 isn't a Prime");
    }
    else if(num == 37)
    {
        printf("37 is a Prime");
    }
    else if(num == 38)
    {
        printf("38 isn't a Prime");
    }
    else if(num == 39)
    {
        printf("39 isn't a Prime");
    }
    else if(num == 40)
    {
        printf("40 isn't a Prime");
    }
    else if(num == 41)
    {
        printf("41 is a Prime");
    }
    else if(num == 42)
    {
        printf("42 isn't a Prime");
    }
    else if(num == 43)
    {
        printf("43 is a Prime");
    }
    else if(num == 44)
    {
        printf("44 isn't a Prime");
    }
    else if(num == 45)
    {
        printf("45 isn't a Prime");
    }
    else if(num == 46)
    {
        printf("46 isn't a Prime");
    }
    else if(num == 47)
    {
        printf("47 is a Prime");
    }
    else if(num == 48)
    {
        printf("48 isn't a Prime");
    }
    else if(num == 49)
    {
        printf("49 isn't a Prime");
    }
    else if(num == 50)
    {
        printf("50 isn't a Prime");
    }
    else if(num == 51)
    {
        printf("51 isn't a Prime");
    }
    else if(num == 52)
    {
        printf("52 isn't a Prime");
    }
    else if(num == 53)
    {
        printf("53 is a Prime");
    }
    else if(num == 54)
    {
        printf("54 isn't a Prime");
    }
    else if(num == 55)
    {
        printf("55 isn't a Prime");
    }
    else if(num == 56)
    {
        printf("56 isn't a Prime");
    }
    else if(num == 57)
    {
        printf("57 isn't a Prime");
    }
    else if(num == 58)
    {
        printf("58 isn't a Prime");
    }
    else if(num == 59)
    {
        printf("59 is a Prime");
    }
    else if(num == 60)
    {
        printf("60 isn't a Prime");
    }
    else if(num == 61)
    {
        printf("61 is a Prime");
    }
    else if(num == 62)
    {
        printf("62 isn't a Prime");
    }
    else if(num == 63)
    {
        printf("63 isn't a Prime");
    }
    else if(num == 64)
    {
        printf("64 isn't a Prime");
    }
    else if(num == 65)
    {
        printf("65 isn't a Prime");
    }
    else if(num == 66)
    {
        printf("66 isn't a Prime");
    }
    else if(num == 67)
    {
        printf("67 is a Prime");
    }
    else if(num == 68)
    {
        printf("68 isn't a Prime");
    }
    else if(num == 69)
    {
        printf("69 isn't a Prime");
    }
    else if(num == 70)
    {
        printf("70 isn't a Prime");
    }
    else if(num == 71)
    {
        printf("71 is a Prime");
    }
    else if(num == 72)
    {
        printf("72 isn't a Prime");
    }
    else if(num == 73)
    {
        printf("73 is a Prime");
    }
    else if(num == 74)
    {
        printf("74 isn't a Prime");
    }
    else if(num == 75)
    {
        printf("75 isn't a Prime");
    }
    else if(num == 76)
    {
        printf("76 isn't a Prime");
    }
    else if(num == 77)
    {
        printf("77 isn't a Prime");
    }
    else if(num == 78)
    {
        printf("78 isn't a Prime");
    }
    else if(num == 79)
    {
        printf("79 is a Prime");
    }
    else if(num == 80)
    {
        printf("80 isn't a Prime");
    }
    else if(num == 81)
    {
        printf("81 isn't a Prime");
    }
    else if(num == 82)
    {
        printf("82 isn't a Prime");
    }
    else if(num == 83)
    {
        printf("83 is a Prime");
    }
    else if(num == 84)
    {
        printf("84 isn't a Prime");
    }
    else if(num == 85)
    {
        printf("85 isn't a Prime");
    }
    else if(num == 86)
    {
        printf("86 isn't a Prime");
    }
    else if(num == 87)
    {
        printf("87 isn't a Prime");
    }
    else if(num == 88)
    {
        printf("88 isn't a Prime");
    }
    else if(num == 89)
    {
        printf("89 is a Prime");
    }
    else if(num == 90)
    {
        printf("90 isn't a Prime");
    }
    else if(num == 91)
    {
        printf("91 isn't a Prime");
    }
    else if(num == 92)
    {
        printf("92 isn't a Prime");
    }
    else if(num == 93)
    {
        printf("93 isn't a Prime");
    }
    else if(num == 94)
    {
        printf("94 isn't a Prime");
    }
    else if(num == 95)
    {
        printf("95 isn't a Prime");
    }
    else if(num == 96)
    {
        printf("96 isn't a Prime");
    }
    else if(num == 97)
    {
        printf("97 is a Prime");
    }
    else if(num == 98)
    {
        printf("98 isn't a Prime");
    }
    else if(num == 99)
    {
        printf("99 isn't a Prime");
    }
    else if(num == 100)
    {
        printf("100 isn't a Prime");
    }
    else if(num == 101)
    {
        printf("101 is a Prime");
    }
    else if(num == 102)
    {
        printf("102 isn't a Prime");
    }
    else if(num == 103)
    {
        printf("103 is a Prime");
    }
    else if(num == 104)
    {
        printf("104 isn't a Prime");
    }
    else if(num == 105)
    {
        printf("105 isn't a Prime");
    }
    else if(num == 106)
    {
        printf("106 isn't a Prime");
    }
    else if(num == 107)
    {
        printf("107 is a Prime");
    }
    else if(num == 108)
    {
        printf("108 isn't a Prime");
    }
    else if(num == 109)
    {
        printf("109 is a Prime");
    }
    else if(num == 110)
    {
        printf("110 isn't a Prime");
    }
    else if(num == 111)
    {
        printf("111 isn't a Prime");
    }
    else if(num == 112)
    {
        printf("112 isn't a Prime");
    }
    else if(num == 113)
    {
        printf("113 is a Prime");
    }
    else if(num == 114)
    {
        printf("114 isn't a Prime");
    }
    else if(num == 115)
    {
        printf("115 isn't a Prime");
    }
    else if(num == 116)
    {
        printf("116 isn't a Prime");
    }
    else if(num == 117)
    {
        printf("117 isn't a Prime");
    }
    else if(num == 118)
    {
        printf("118 isn't a Prime");
    }
    else if(num == 119)
    {
        printf("119 isn't a Prime");
    }
    else if(num == 120)
    {
        printf("120 isn't a Prime");
    }
    else if(num == 121)
    {
        printf("121 isn't a Prime");
    }
    else if(num == 122)
    {
        printf("122 isn't a Prime");
    }
    else if(num == 123)
    {
        printf("123 isn't a Prime");
    }
    else if(num == 124)
    {
        printf("124 isn't a Prime");
    }
    else if(num == 125)
    {
        printf("125 isn't a Prime");
    }
    else if(num == 126)
    {
        printf("126 isn't a Prime");
    }
    else if(num == 127)
    {
        printf("127 is a Prime");
    }
    else if(num == 128)
    {
        printf("128 isn't a Prime");
    }
    else if(num == 129)
    {
        printf("129 isn't a Prime");
    }
    else if(num == 130)
    {
        printf("130 isn't a Prime");
    }
    else if(num == 131)
    {
        printf("131 is a Prime");
    }
    else if(num == 132)
    {
        printf("132 isn't a Prime");
    }
    else if(num == 133)
    {
        printf("133 isn't a Prime");
    }
    else if(num == 134)
    {
        printf("134 isn't a Prime");
    }
    else if(num == 135)
    {
        printf("135 isn't a Prime");
    }
    else if(num == 136)
    {
        printf("136 isn't a Prime");
    }
    else if(num == 137)
    {
        printf("137 is a Prime");
    }
    else if(num == 138)
    {
        printf("138 isn't a Prime");
    }
    else if(num == 139)
    {
        printf("139 is a Prime");
    }
    else if(num == 140)
    {
        printf("140 isn't a Prime");
    }
    else if(num == 141)
    {
        printf("141 isn't a Prime");
    }
    else if(num == 142)
    {
        printf("142 isn't a Prime");
    }
    else if(num == 143)
    {
        printf("143 isn't a Prime");
    }
    else if(num == 144)
    {
        printf("144 isn't a Prime");
    }
    else if(num == 145)
    {
        printf("145 isn't a Prime");
    }
    else if(num == 146)
    {
        printf("146 isn't a Prime");
    }
    else if(num == 147)
    {
        printf("147 isn't a Prime");
    }
    else if(num == 148)
    {
        printf("148 isn't a Prime");
    }
    else if(num == 149)
    {
        printf("149 is a Prime");
    }
    else if(num == 150)
    {
        printf("150 isn't a Prime");
    }
    else if(num == 151)
    {
        printf("151 is a Prime");
    }
    else if(num == 152)
    {
        printf("152 isn't a Prime");
    }
    else if(num == 153)
    {
        printf("153 isn't a Prime");
    }
    else if(num == 154)
    {
        printf("154 isn't a Prime");
    }
    else if(num == 155)
    {
        printf("155 isn't a Prime");
    }
    else if(num == 156)
    {
        printf("156 isn't a Prime");
    }
    else if(num == 157)
    {
        printf("157 is a Prime");
    }
    else if(num == 158)
    {
        printf("158 isn't a Prime");
    }
    else if(num == 159)
    {
        printf("159 isn't a Prime");
    }
    else if(num == 160)
    {
        printf("160 isn't a Prime");
    }
    else if(num == 161)
    {
        printf("161 isn't a Prime");
    }
    else if(num == 162)
    {
        printf("162 isn't a Prime");
    }
    else if(num == 163)
    {
        printf("163 is a Prime");
    }
    else if(num == 164)
    {
        printf("164 isn't a Prime");
    }
    else if(num == 165)
    {
        printf("165 isn't a Prime");
    }
    else if(num == 166)
    {
        printf("166 isn't a Prime");
    }
    else if(num == 167)
    {
        printf("167 is a Prime");
    }
    else if(num == 168)
    {
        printf("168 isn't a Prime");
    }
    else if(num == 169)
    {
        printf("169 isn't a Prime");
    }
    else if(num == 170)
    {
        printf("170 isn't a Prime");
    }
    else if(num == 171)
    {
        printf("171 isn't a Prime");
    }
    else if(num == 172)
    {
        printf("172 isn't a Prime");
    }
    else if(num == 173)
    {
        printf("173 is a Prime");
    }
    else if(num == 174)
    {
        printf("174 isn't a Prime");
    }
    else if(num == 175)
    {
        printf("175 isn't a Prime");
    }
    else if(num == 176)
    {
        printf("176 isn't a Prime");
    }
    else if(num == 177)
    {
        printf("177 isn't a Prime");
    }
    else if(num == 178)
    {
        printf("178 isn't a Prime");
    }
    else if(num == 179)
    {
        printf("179 is a Prime");
    }
    else if(num == 180)
    {
        printf("180 isn't a Prime");
    }
    else if(num == 181)
    {
        printf("181 is a Prime");
    }
    else if(num == 182)
    {
        printf("182 isn't a Prime");
    }
    else if(num == 183)
    {
        printf("183 isn't a Prime");
    }
    else if(num == 184)
    {
        printf("184 isn't a Prime");
    }
    else if(num == 185)
    {
        printf("185 isn't a Prime");
    }
    else if(num == 186)
    {
        printf("186 isn't a Prime");
    }
    else if(num == 187)
    {
        printf("187 isn't a Prime");
    }
    else if(num == 188)
    {
        printf("188 isn't a Prime");
    }
    else if(num == 189)
    {
        printf("189 isn't a Prime");
    }
    else if(num == 190)
    {
        printf("190 isn't a Prime");
    }
    else if(num == 191)
    {
        printf("191 is a Prime");
    }
    else if(num == 192)
    {
        printf("192 isn't a Prime");
    }
    else if(num == 193)
    {
        printf("193 is a Prime");
    }
    else if(num == 194)
    {
        printf("194 isn't a Prime");
    }
    else if(num == 195)
    {
        printf("195 isn't a Prime");
    }
    else if(num == 196)
    {
        printf("196 isn't a Prime");
    }
    else if(num == 197)
    {
        printf("197 is a Prime");
    }
    else if(num == 198)
    {
        printf("198 isn't a Prime");
    }
    else if(num == 199)
    {
        printf("199 is a Prime");
    }
    else if(num == 200)
    {
        printf("200 isn't a Prime");
    }
    else if(num == 201)
    {
        printf("201 isn't a Prime");
    }
    else if(num == 202)
    {
        printf("202 isn't a Prime");
    }
    else if(num == 203)
    {
        printf("203 isn't a Prime");
    }
    else if(num == 204)
    {
        printf("204 isn't a Prime");
    }
    else if(num == 205)
    {
        printf("205 isn't a Prime");
    }
    else if(num == 206)
    {
        printf("206 isn't a Prime");
    }
    else if(num == 207)
    {
        printf("207 isn't a Prime");
    }
    else if(num == 208)
    {
        printf("208 isn't a Prime");
    }
    else if(num == 209)
    {
        printf("209 isn't a Prime");
    }
    else if(num == 210)
    {
        printf("210 isn't a Prime");
    }
    else if(num == 211)
    {
        printf("211 is a Prime");
    }
    else if(num == 212)
    {
        printf("212 isn't a Prime");
    }
    else if(num == 213)
    {
        printf("213 isn't a Prime");
    }
    else if(num == 214)
    {
        printf("214 isn't a Prime");
    }
    else if(num == 215)
    {
        printf("215 isn't a Prime");
    }
    else if(num == 216)
    {
        printf("216 isn't a Prime");
    }
    else if(num == 217)
    {
        printf("217 isn't a Prime");
    }
    else if(num == 218)
    {
        printf("218 isn't a Prime");
    }
    else if(num == 219)
    {
        printf("219 isn't a Prime");
    }
    else if(num == 220)
    {
        printf("220 isn't a Prime");
    }
    else if(num == 221)
    {
        printf("221 isn't a Prime");
    }
    else if(num == 222)
    {
        printf("222 isn't a Prime");
    }
    else if(num == 223)
    {
        printf("223 is a Prime");
    }
    else if(num == 224)
    {
        printf("224 isn't a Prime");
    }
    else if(num == 225)
    {
        printf("225 isn't a Prime");
    }
    else if(num == 226)
    {
        printf("226 isn't a Prime");
    }
    else if(num == 227)
    {
        printf("227 is a Prime");
    }
    else if(num == 228)
    {
        printf("228 isn't a Prime");
    }
    else if(num == 229)
    {
        printf("229 is a Prime");
    }
    else if(num == 230)
    {
        printf("230 isn't a Prime");
    }
    else if(num == 231)
    {
        printf("231 isn't a Prime");
    }
    else if(num == 232)
    {
        printf("232 isn't a Prime");
    }
    else if(num == 233)
    {
        printf("233 is a Prime");
    }
    else if(num == 234)
    {
        printf("234 isn't a Prime");
    }
    else if(num == 235)
    {
        printf("235 isn't a Prime");
    }
    else if(num == 236)
    {
        printf("236 isn't a Prime");
    }
    else if(num == 237)
    {
        printf("237 isn't a Prime");
    }
    else if(num == 238)
    {
        printf("238 isn't a Prime");
    }
    else if(num == 239)
    {
        printf("239 is a Prime");
    }
    else if(num == 240)
    {
        printf("240 isn't a Prime");
    }
    else if(num == 241)
    {
        printf("241 is a Prime");
    }
    else if(num == 242)
    {
        printf("242 isn't a Prime");
    }
    else if(num == 243)
    {
        printf("243 isn't a Prime");
    }
    else if(num == 244)
    {
        printf("244 isn't a Prime");
    }
    else if(num == 245)
    {
        printf("245 isn't a Prime");
    }
    else if(num == 246)
    {
        printf("246 isn't a Prime");
    }
    else if(num == 247)
    {
        printf("247 isn't a Prime");
    }
    else if(num == 248)
    {
        printf("248 isn't a Prime");
    }
    else if(num == 249)
    {
        printf("249 isn't a Prime");
    }
    else if(num == 250)
    {
        printf("250 isn't a Prime");
    }
    else if(num == 251)
    {
        printf("251 is a Prime");
    }
    else if(num == 252)
    {
        printf("252 isn't a Prime");
    }
    else if(num == 253)
    {
        printf("253 isn't a Prime");
    }
    else if(num == 254)
    {
        printf("254 isn't a Prime");
    }
    else if(num == 255)
    {
        printf("255 isn't a Prime");
    }
    return 0;
}

生成器二号：从 if-else 链进化成查表

if-else 链只是开胃菜。二号生成器更进一步——把质数表直接做成 char 数组写进源码：

sprintf(temp, "char isPrime[%d] = {", maxnum);
fprintf(fp, temp);

for (int i = 0; i < maxnum; i++)
{
    if (isPrime(i))
    {
        fprintf(fp, "1");
    }
    else
    {
        fprintf(fp, "0");
    }
    fprintf(fp, ",");
}
fprintf(fp, "};\n");

生成的 example2.c 里是一个巨大的 char isPrime[] 查找表，运行时 if(isPrime[num]) 一次数组访问就出结果——这才是字面意义的 O(1)。

而 main 里写着它疯狂的一面：

int main()
{
    chouxiang2(INT_MAX);
    return 0;

INT_MAX——二十一万万一千多万的表。文件夹里那份 157MB 的 example2.c 就是这场豪迈远征的遗物：全量应该是 2,147,483,647 项（约 2GB），磁盘先扛不住了，留下了一份 157MB 的残卷。开头还是对的：

1	char isPrime[2147483647] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,...

isPrime[2]=1、isPrime[3]=1、isPrime[4]=0——质数表的前几个字节完全正确，然后永远停在了第 157MB。

这算 O(1) 吗

算，也不算。运行期的确是一次查表，O(1)；但把预处理、生成、存储的成本全算上，这是一个把计算成本转移到过去的方案——本质就是查表法（space-time tradeoff）的极端表演。它的实用价值约等于零，但它把一个重要的事实演得明明白白：判断可以变成记忆。数据库的索引、编译器的预编译头、浏览器的 DNS 缓存，全都是这个思路的正经版本。

系列其他文章见抽象代码宣言。