primes_bootstrap.py

#!/usr/bin/python3

import os
import sys
import re
import itertools
import base64

template = '''\
#!/usr/bin/python3

import base64

def convert(data):
    data = base64.b64decode(data)
    a = bytearray(len(data) * 8)
    for i, b in enumerate(bytearray(data)):
        for j in range(8):
            a[i * 8 + j] = bool(b & (1 << j))
    return a

# The Table of Odd Numbers containing First 10,000 Primes
table = convert(b"""
%(data)s
""")

def primes():
    yield 2
    for n, b in enumerate(table):
        if b:
            yield n * 2 + 3

def main():
    print(sum(primes()))

if __name__ == '__main__':
    main()
'''


def primes():
    # The First 1,000,000 Primes (from primes.utm.edu)
    with open("primes1.txt") as f:
        f.readline()
        f.readline()
        for line in f:
            for num in line.strip().split():
                yield int(num)


def main():
    sub_primes = tuple(itertools.islice(primes(), 0, 10000))
    max_prime = sub_primes[-1]
    data = [0] * (int(((max_prime - 3) / 2 + 7) // 8))
    for i, n in enumerate(range(3, max_prime + 1, 2)):
        if n in sub_primes:
            data[i//8] |= 1 << (i % 8)
    data = base64.b64encode(bytearray(data)).decode()
    data = re.sub(r'(.{76})', r'\1\n', data)

    print(template % {
            "data": data,
            })


if __name__ == '__main__':
    main()

primes_generated.py

#!/usr/bin/python3

import base64

def convert(data):
    data = base64.b64decode(data)
    a = bytearray(len(data) * 8)
    for i, b in enumerate(bytearray(data)):
        for j in range(8):
            a[i * 8 + j] = bool(b & (1 << j))
    return a

# The Table of Odd Numbers containing First 10,000 Primes
table = convert(b"""
t2VaMk2JtkAZJiXDBkHLkGQaAi2QsERSogjDlGhBFCUYICGZkEwahCWDEiFCJEWKAiEYNgRaoAVQ
hCgJlESCMkwYJkBLIgnAECGJoGSCEGCZFkwAgCQChEBLNEHYEgQRpERRoCwTAkgDoCEYIkmANAhB
BATShiAJMGAAEmmRMARCgg3BgGmIAAFQImARsEgKBiBTAmlKkARKECkABAhRJgDBgCgIhEXSEk0Y
okAIpgGBEilAhCRCECgZAAxRoAgSlADCgADQIAWJIgAbBACTlEHBMGBAAgiINgARJCwTBmEIpEQS
ECyQIkQSgAyBEmAINASKAGUZFEAAgiUTgAlIMEHAEmiAAAgZhiHDkAgAhCESAiQIBkhJgCGQFgCD
BEQSIGCZhARBgClABEDLoEAAICQIJARLJCyQlGFAEAFKMEkAkEARIgjQAiDIgCQQAgUAkkQapAlA
FmDBFACSIgQABEwbAilCAmgCAEVIIkGZMgxIAAWBACABFCBSAkkYgghDBCEAFikChGRCMCSJhEwS
IgASgAGKEACIAA2ZAkQQICCDhGFCoAAYMAwBtAhIBgFRAgDDlEQKEkGBIARAggxABAgJNCFSAgCB
MAgDBgiAAAkIkAHKECGJMgxKBgUClACKFAVSIGgAoABIgiCQFiBBpGAQAAiYAAQSgixCEgCBFEGA
MCwBpEALJAiAkAgDAGVQIAEAgkhYACEChkCDBCSKEkmQkghQAAVDhmABJACQIgQZAEwDggkRAEEC
pEAKIkEJEgwIoCFAFGgCkEASMmwAlgQJhCBRAACBIGWQIGCIAAxSAgxSEAlKkEFQIAEZIkACAAwA
BiBDMEUAMkSJggBBACXRgGCIsASCAEQAsABaIASDgAFABCBKAkWQFEABBimBACFCAEBCMgEZJAAY
IiCREAABhGFQAmgQIAwLICAAFClIBEGKAAwIhARBIAVQkElABGAAECmAggAIoAgDBkEAgCVIIk0A
FEBIAiWDhCEBFACaAAyAsgRAogEAEgHBMCSKIAAJFAAahCiCAglIlERCMAmIJAgToCRBgEiIAAUS
IEQIJggCAChRFiBIJAXYACgJBABSggRQFEkBgCGIEAGQoEAZAAQCBimAkCRCEAiBgEAIJCCRgADC
tGCYAGQBIkQAhgCBFmCJMABQAGAYoAAJhAUQAEBKoABCIAAZAAhCgAUSgACDFEXCIEAIBARKpgHA
ACBLoCAQECiRkkRRICBSEAFDlACQECUIBAAKBCCCEiGBkCEIAkmAkAhQJgyRhAHCoEQIAkERkgAK
BARChGCABCHYIEUBAEAbgiRQkkgAAAHKIEmBAAQDhASAAGgLlERAMAAAtABIBiiQACBAICGYIACQ
kkADoCQAhACJJABQEAyYggBTAAgSFAABEGQQAEQJBkhJAAGTACGLJAACEiGBAERABg1ABAgAMAFK
IkSAtAgYBAlQkglCAEGAMmAIFAAYggGQgAiDAGRAAGEQBAhBhgkBBikDIADYMCCIAExDAghCBEkK
sCDAIA0IgkARoCCQFCmAIAQaMAgAlAAIIABCBCFIECQCAikBAAQQAgDBBgBBIAGIAiQQoEwAgAAD
EmAANEGCEAkIIgQCACBTEGiLhGSSIAEQhgRJIAkAACCAhCFCEEyBgAgSgCESgAFIhCAYEiwQJkBB
BAiSkkCDoAQIEAwIIkAIACWShgBKFEAYAGABMAhCBgGABAHBAAQIAmEQtAQDAgwAgAhIhAWIEEEB
BghbBAATgCCBACWSEA0QEkAAIgGAFiABgEVKEAgAEEhToAkAlgjDsADAIAgBgkAYJCQQFCjAEEUI
AgSIBAgIJCFQBkFJMGCQAmkQoAAAAgTBFkEBACTAICQIgEgCggFCAGECNAAAMmARIAQZogRDgEgB
lAAAMiQAEghIgCGAECnDoEVIECAQBEQCogkQAAFCsEBIEiAYAAQIBASBAAgCkCFaIEgJtABAJgwA
BGCJJCAIEg2AoEQSJggAAimIBCWQICSRtAgKBAgDEkBCFAAIACCIAAQTBCQDFACKACFCAgUQgABB
BABBEgkCICBQIEgIAkgRIAgQFkAIlCEAAiyAgEAIpASQkEECACFSIgAANghQIiRAgEFApGQAAACB
AghYggmCFAhJIAQCIkERgAwQgAyQgEBIMEWAIGCBIggCAAHRBCCIkCSQACEYFgAKogARAgFJhESC
EECIggAQoCBAAgCJBCBYMiyZAARIgCCChGDAMARIAE0AkgAJBAGTAkEDBAQAECQQAAwSpAEBgAiA
BADCACWIAEwAAgxDAGAAkEBAAgiYAgBaBiXBlEgBFAAQImAAlkhAoABRAAmChGEQAAQBBggRAgAA
lghDAGAAAAkZoERAICCBAihDMEFSMAWJJkBIBAnABAEKpAASEEUAIkgCggABgGgJAAUCIACZkEAS
hAxCEAEChERAEgEBNAxBIiGAECAAlADAIkEQoAhABgEAEiDIACAQECgQlAwAoAQQBEACMCBAEASY
pAQagAgSEkGAIGEAAkkBEkAABgFQgAADsCCCEGiAgAAAJAlCgkgJBAASIgCJIAwThiBAACkCkAQA
EkgQJAwBgAHRBGgKAEXCEiUAEEwKIADRAgAAACCKACwQFkBCgAQQkEgBBAHYIAQYgAQIAAyBEAEB
AAASIgQJMABZIgkBBmBAIGQQAiiQAgBYggWClCmAMCQYAEGQFAALgCkRkCEIJABAAmkAIABRogHA
FAACBGACMiAYlARCIijAEAFJAGAIMEQRBEAAAAxCgkFLgECQAgGAIkRCgCgQkCjDoCVKAEAAhAgQ
JixAggEDkESAAgSRAkgAIADBBCgAAADQIGEQBAALBCCTEGhIhEDIIAABIgQIBgXDBEgCAGRQAgQY
kERCgAgRFiAABAHYACSBgAQQggECAEABMCGYECUIogQBgAASAAnBEEBSEAgBgkhQIAwCAAGDtASA
AiyBAAAAJAAAgAFJEACaAGQQJAQYBCFAkEhItAACIAmBMAAJhABQgAiCECQCEkkAhgBCAgCAAAlL
oADQIEQRFEQAIiFAEgmKACFIMA0IgkAIJASDlEEBIAESMkCIAkAIIAEBBCHCgAQQAigAsAgYoAkB
gkCABASQIiWIMEgTBgSBkEgAMAECAAEABgQDBCRChAgBAEBSAC0QAEQCAgGABAAKhCQKEGQAgkhQ
oCxAAAkIAEDAMgAAAgBAoAyAkAFCMGACEg2JMEBABAGCBCEJEAQaAkiQgABQgAUAhEhJIAEaIESI
sAwBACCCEmBANASCEEARAgBQhgBCkCAABEUAEEUAJEQCgghBBCDDhCRSIACIgABRAihABkAAJEHQ
AAyJoAACpCAAkgAAAEQKAAEAtAAQBCURhEFAgESCAGEAAAAaAgBBFAGBICXIAkGBBEASgiCAAElA
lAAKACgQJghYgiHSEEiCAAEAIiQAMgQDACEQBAHJACUAECiZEkgRggQAhAjAkACIAgAZBERKBASS
hmBAoAUQIAwJAgARIAiTgmBBgAAYEgGRIAQSJA2AEmkJFCEAAiCYIAABgAkQkmhChERAAikAIgxS
AAADkEiIBCEQEiAYFABCICBABAiCBAQCIAQRgAwBAABAFgGBkABIECAABgAaJCyQgCECEEAKAEiA
tggAACAQgAEIIESYAiWAMggSBAxClAFAECFYIACItAwCAABAAmECgACAAgCREgRLAgERAGiIlABQ
MAQIggALIggBFAFBJCBCEEgRFEACACACEgDAlAEIMCQAgEBQgCgQhmiAgCAQAkkAAAhJACGCggBD
IEAIECmQEAAIJAUBAGiJICRAAgAApAQRAgASgCEIMAUAIgkQFgQQIgDCBCADhGAAIEAQAEwJJAhR
EABCJGAIEEgJBExBAAVQggEAlGEAIiEIAgQCIACAAgiAkAFAAkSJNAgAAgQCAgFCpCQCEAwBMkAY
hAABACmJJASQIEQIJAQagADDAmgAgEHCECCBIAhAJCBRkCgAgCSAAEgQIAwBIAGRAiBABEEIEAyA
ggBBICwAgkDIlABQMgARoABRAAyCBgAAMEBKMEGIBkAYBgkQAAAJIGCQECyBIAhAogEBggnIFAQA
ImCAEAATAA3AgAkKEAUKEACZMAQAICGQBECDgEBAMCEANEhBBCFAAgHAhAUCAEwAhkADIiRClAFJ
gABAIAUAhkABhCgCFEgBkAQIMACAhEBQBgDSBAABFEAQAAEBgkAKAgCChAgJMCCQACQYoAgABAVD
AAACsECCAGiBIAxIAAUQgGCDAARAMmUIgkxApABBEChIJEBCEEgRgAwAAgwQEghDIGEAEgkIIgAL
BAgSAAmDAARIAAmBJghAICgRgCGIAACYEAUAgAAKAAhCgmCIFAWAAEUAkAAJhiQQgkAApAACMEAJ
BgQIJCUCFAgAFCDCIigIMAgDogDABADDACFQAEiAAkgRoCAABEABBGCAACyYpAQKgCABBgFAoEQA
EgSIAkgZIAVBBACJMACCEAARAggSBAWCAAgAECBCAkQREEgJgCkDkgACoAUKMEGBBghIBgSQBACK
BEBAEkEAoAABogAQBiBCIAWIIACYggRAIgQQEAGApCGQEAAQgABbBCACBAHAgCBAIAQIEgAQAgnD
BGCJkEAKAgABkERaIglAgGiANCBAACEJAAwCgCSDEAECFAHCAGAINAAQBCAAhEiIgEASAmkIJkRD
AAhABgEKAEVIIAyQEEBSACwSEAgIsGCYICQBpAQAoASBgghBECUQEgwBBggRBgUCgAEDJCQCAgGA
EEBCAAwABgGJAACKAkGIoEQJBCDSkABCJAEIMCABFAAKBCBQkCgJAGGAAA0YoEQJJgFAAACKgADQ
EAyREAwDoABAAEgCJAEYAgSAAkQSBCQCEgEDAEAAAACIsghIAAVBgmECMCQSAkkBIkRAIAyDFECI
AAAAImSIkEQYgCXQAAgKAAFKIACQMgBRBiARkEAJEEGCAAgABEQAgAhAAiFAoCAKACAZFkASggwA
gEgAkEGAAiCQhABCICAQkAgAoCBIEAAAIEhJJAwDhEBApAAaEggQAgAQAgyDFkiIAABIAAWRAAAR
gAjCgAAAEEQAIgCRAABTIAEDkAiAAGRQAkUAlAxAAClQEgmJBASSACQAAgASIAFCBAACJCBIMAWR
AEQKhAABhGkAEGBIEggAgABYBAVQAECAgAQAECmBEgASAgFCEghJIAFQIAARhAgChAARACEKgATI
EAAYNgAABgCRBEgIFCAAEGAQAEgAoADBAgmJhGCCMEABlEASgCQCBAjDlCDAEAWYJERIgCCClEDA
oAQAIAkIIAAIICSBAkCBECAQACwQMABIJABAFGBAJAAAIkABgAQDAAmBAAAIhEGIIgkAFgQCIgAQ
EGAIkACAAmQQAkwIBAgAEgELIESAMEQJEkBTACEABAgDJCBQACgQgkBSIAwABAjAgEUSMEGIoEAJ
IASThgGAgCCAAGUREAgQgAxAEmAIACBKAAUJNAAIgChBACBAAEAAIgCAFAxKACFAgEgBECGQIggY
kAgIAiEAECiIIGEQACQIAghDIAkAFEFDoAAQIAiJggRAgAiDgiADsEFAIAwIEABQAghAhCELJACK
EgSREEQYggRBAAFAACEQImSBJEgQAiEQECEANAVKEAkABAgSBATBACCBEADAEkEAAgwABAhAAAFC
AADSACgZEghRAAQCAgFIACFQEAyIJEAJBCADAEDAkCVCAAEBgAgRBgCSAABCBGQQACwBgkRYAACA
AigAECUYAEWAlAgbAAABAgAIAAQAIiCQIAAYgAUBgCALhAECEAQYAgQApAkBBCFBAEEaMCCBBkxA
oghAgAiKBEAAMggAJAQZgAwSgAgCMCRAMEGAFEAAIgiAgEAIAASYAmEQggwIJghDBkFAACGIAEAI
lEgBBAiAgmgAJADCMkkBMAQTIiHAFEAAhGCQACgAgEBABCDRBCCAgCDAICAJEkwQIiASEEFJAEFQ
AigYJgAQgCwAAGEDMGBCAAmAgkBQAABCACCDoAQAAkWAAABKAA3ChCBBJAFQACCABAAQBilSEAlK
oACCEmABBgQBgCQCACACAAASECAQJEABhAkRACgIIEESACAJkAhBIiwAEgHIICFIACQQBABQAAwR
EggBAEUIAkCAEkABJCADAEHChCCaEASAAEQKJAGAEmgAMAGIAgQIMEgBhCQQgkEAIABAEGkYEAwR
IABSECgKlASQIkAAAAALogAAFAACICDIIAiYFAQCIggQkAgJhGBYACQAAARAhCSDAkkAkCEIEkAJ
NAhBACSSAiAIICAQAAiQAkBQpgFABADAEAWQAGEBAEACBCkDkEAAIATAEAEBBghAhCRQBGiAAAFS
AAQYkAQIICCAAimAAGFCAAwBkARAggFAEEiCBCAIIgCAgkABhCAAlmBDEAASEEWIBAAYBARAhgGK
BGSSAgWQAkgQgAzBFEGBIAQKAkAIFAASAChAgEhAhECIEEAAAggYICXBEACKAAESICUAEkAAgAAQ
BgBBhGACMAiYhEBAACkAAAmJgAAAMCUJBAQKICwChCAAgCEAAEQBBEBABCDRBCCJAGAIEEgBIgQK
IgSBBkEJEAAIAgCQIAwQgijSAAgCtAEAACCIAAhLggWSgGABAAVAEmEAAgQBJABQACALpEDAIEwQ
hEQAIggSkAABBCDAAAwYgEAIIAQAFCEDkGBaIAiAMAhYAgnBgEAAgGCSAggBIAhahA1AEihAEAAS
ImABhAQAgCERAEFKMACIIECABAAAIiTQlAAAECHCACUIFkAIgigABAhAJCAQMECYhEADAC1CBgEJ
AACAMAgRpEBYpAASBCABAGEIAgkAAgBIBiURgAHCFECIEgiQAAAQgA0AFiBJMABCAAAZhAAQAAEC
kkAABEWCIiCAAAAIAAXTEAgLAEEAMCAAJExIJAlBAggAgAAaECSIAgxCAAgCBgiAoEAAAgiBoABB
hCABgEABkABAMgEIAEhJAAFDBGFCBAQAEGkAMAAIhgRCkkiBACUYAkQAIAAABiiBAClIkEAIAAkY
EAAYBgCABACBhEGAICEIAkhDgiAQBADIICRSEACAhAADgAkCAAFDNCBAACgRIAAJoAQTFCADEEQC
AgQAggAYJiUAgEACMAAAAESQMAAAIgHAAkmAEAWKAECJJEALBAHCgiFCIAQIIiEQIgATgCARBAAD
AACCAkQIhEBBACAAEikCAADQEEQIggADoAhAEEDBIGAAMAEQBgALoCCBEghAAARQIAkBgAgBJgGT
BkADIGSYAESRAgxQBASAEgEIICBKACQQBAwKhAUBAgBCIACCAACIAABBoAADgCCAhAEAECAQFABA
BiCBEAABAGDAAACRFggAgAgSAAHKtAEQIgmBBAQIBAiAkiiAkGBQIEmBgAAAAilQAiAKIASCAAAR
kgQKBAkBAiHIJABYAGQRkAAahggAAABIBAWCMEgIEAAZIgEBFEiClEUAEg0IEEgAAiFQFghBBESI
AAgAgAQToAUABgCKAEHQAgEABAQYhAQBBkgCECAAAAkBhkhAAARSAgEBkCCCEAgAAAwYgAzDFEBI
ACCSAgCRJAABACySAkEIoAUAEggIAgBLBABCBAAIEEQAAigQAkhDoACQAACCAEXKACAJgAgBIAFQ
BEAIoCEQMCkRIAAIJCCQkmjBIEEAMEEIFAAAJAyCAEDBhGAYEiGBgEgQhghCgGgBIAFIIGQAkAgA
ACQBkkgIMEGAEEEAIAxLgAUQlAgAkARAEAEABExLAAmAFiCABCACAAABBgQQgAEQgAEBEEDAIgyB
IkBRIAyAgEhAAGEKAAwIAEgQAiCCAAGDFGQAEGAAkkxAIAGAgGHBIAQSIgAYAEACAgUQACkKEAXK
AAgIFAAChgCAlCABAETQIgUQhAAIBiHBBChJBEBCEAAIhAgSggFSFAABFCGIICCBogABAACSEgkB
IGQYEgCAoAgBJAkQBgGDoAAQEkCAAAAIIgQDBGEIACWIAgCZgAAIgABBEClCpABCACgAMggAAAFS
AEgAkCGSEGEAFkAJACBQAAFIICFaIEAAgAhAIARAhgkBIEAIEAABBkAAACwTAkCCIAUAMAQBsAhZ
ACwAgAEIBECAAACQMAACgg1DFABAFARIAgGYAEgIgAACkEAAAAFAIgGQIAAYoAUQgAgDFCEQEkkQ
EARCgCEAAiDBACSAACyYAAASgAwAggALpGHAEAkBggRKgCAAlEBCsCEAIgQAhAgZIAgAAgADlECK
AEQAIEAIAA1AFCkAFAQQIEEIsAwCgASQgEhKAEEKIAEJAAgBBgEBkAgCACSAAAwIpEACIABQBAkI
IAQaEAyRAEAQAiFCFghDAECAIgAIoABSACASgADBECRAAgAAkEBJIAAShCABEASIAG0AIgxCIA0C
AADJJAAQIkGBBAQRAggQkmAItAAIIkAREAhCgCACFCgDECBCAGgApAQBoAgBEgjBIEUQMGQAFggQ
ggBCFgiKMAEAMiCIAEQAIAyAAiGAgAUQEkUBkEABACWQBiAAAACYACgQIAgQpADAgAEIBARIAAAJ
MEQTAAECAEkAgEACAAAYEAQCIgDQhGAAkEAQAAQIoEhKBCABEAmCBAUQAAAIEAgDoAEQgEBIAEDQ
MCwJgkASAAyQFACDIAVAAEwBAEgIBgUQgGBIgAAAEEwQgEBIhgCBAkBAEAEaIiUJ
""")

def primes():
    yield 2
    for n, b in enumerate(table):
        if b:
            yield n * 2 + 3

def main():
    print(sum(primes()))

if __name__ == '__main__':
    main()