ASIS CTF Finals 2016: SecuPrim

,

$\mathrm{ans} = \mid{ n \mid l \le n \le r \land (\mathrm{isprime}(n) \lor \exists m \lt n. \exists k. n = m^k ) }\mid$. This is done by simple implementation.

#!/usr/bin/env python2
import gmpy2
import string
import itertools
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='secuprim.asis-ctf.ir')
parser.add_argument('port', nargs='?', default=42738, type=int)
args = parser.parse_args()
context.log_level = 'debug'
p = remote(args.host, args.port)

# proof of work
p.recvuntil('ASIS needs proof of work to start the Math challenge.\n')
_, salt, _, prefix, _ = p.recvline().split('"')
prefix = prefix.rstrip('.')
log.info('salt: %s', salt)
log.info('prefix: %s', prefix)
letters = string.digits + string.ascii_uppercase + string.ascii_lowercase
try:
    for a in letters:
        for b in letters:
            for c in letters:
                for d in letters:
                    x = a + b + c + d
                    if hashlib.sha256(x + salt).hexdigest().startswith(prefix):
                        raise StopIteration
    log.error('Proof-of-Work Not Found')
except StopIteration:
    log.info('result: %s', x)
    p.sendline(x)

def is_valid(n):
    n = gmpy2.mpz(n)
    if gmpy2.is_prime(n):
        return True
    if bin(n).count('1') == 1:
        return True
    for k in itertools.count(2):
        root, rem = gmpy2.iroot_rem(n, k)
        if root == 2:
            return False
        if rem == 0:
            return True
while True:
    p.recvuntil("What's the number of primes or perfect powers like n such that: ")
    l, _, _, _, r = p.recvline().split()
    l, r = int(l), int(r)
    log.info('l: %d', l)
    log.info('r: %d', r)
    ans = 0
    for n in range(l, r+1):
        if is_valid(n):
            ans += 1
    log.info('result: %d', ans)
    p.send(str(ans))

p.recvall()