Backdoor CTF 2013 杂项 75

0x00 题目

H4x0r曾在他的博客上说道，“时间最终赶上了每个人,除了H4x0r。如果你能挑战我!”

来吧:时光穿梭门

0x01 解题

打开传送门之后，题目要求在3秒内提交前N(比如：30个)素数的和。

第一种方法的算法思想就是简单的素数判断方法

import re
import httplib
import urllib, urllib2, cookielib

def find_sum_of_first_N_prime_numbers(N):
	sum = 0
	n = 0
	num = 1
	while n < N:
		# prime numbers are greater than 1
		if num > 1:
			for i in range(2,num):
				if (num % i) == 0:
					break
			else:
				sum += num
				n = n+1
		num = num+1
	return sum

conn = httplib.HTTPConnection("hack.bckdr.in")
response = conn.request("GET", 'http://hack.bckdr.in/2013-MISC-75/misc75.php')
response = conn.getresponse()
text = response.read()
num_in_page = [int(s) for s in text.split() if s.isdigit()]
N = num_in_page[1]
sum = find_sum_of_first_N_prime_numbers(N)

headers = response.getheaders()
cookie = headers[2][2]

headers = {"Content-type": "application/x-www-form-urlencoded"
			, "Cookie": cookie
			, "Host": "hack.bckdr.in"
			, "Connection" : "keep-alive"
			, "Cache-Control" : "max-age=0"
			, "Origin": "http://hack.bckdr.in"
			, "Referer": "http://hack.bckdr.in/2013-MISC-75/misc75.php"
			, "User-Agent": "Mozilla/5.0 (Windows NT 6.3; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/41.0.2272.118 Safari/537.36"}

params = urllib.urlencode({'answer': sum, 'submit': 'Submit'})

response = conn.request("POST", 'http://hack.bckdr.in/2013-MISC-75/misc75.php', params, headers)
response = conn.getresponse()
print(response.read())

但我感觉这个算法效率太低，如果题目给的数字很大，验证时间再调小，这个算法就不再适用了，根据素数判断算法(高效率）一文编写了另一个参考示例：

首先生成质数列表：

import math
import time
start=time.clock()
n=10000000
result = list()
result.append(2)
result.append(3)
for i in xrange(5,n+1,2):
    for j in xrange(3,int(math.sqrt(i))+1):
        if i%j == 0:
            break
    else:
        result.append(i)
end=time.clock()
print end-start
f=open(r'prime_number.txt','w')
for x in result:
    f.write(str(x)+'\n')
f.close

主要用到算法思想:

判断一个数是否为素数只需除以这个数的平方根+1之间的所有的数
从2开始往后依次增1的数列里所有偶数一定不是素数(这能减少一半的时间)
素数快速筛选法

测试了一下(CPU:Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz System:Windows 10 Pronfessional x64)，生成前10000以内的素数平均0.02秒，生成前100000以内的素数平均0.3秒，生成前1000000以内的素数平均7秒，生成前10000000以内的素数平均140秒，速度还是可以的，但是这肯定不是最优的，应该还可以进行优化。

然后是读取素数表计算前N个素数的和并提交结果：

import requests
import re
import time

def main():
    starttime=time.clock()
    url = "http://hack.bckdr.in/2013-MISC-75/misc75.php"
    req = requests.get(url)
    tmpcookies = req.cookies
    match = re.findall(r'[0-9]+', req.text); num = int(match[1])
    try:
        src = open("prime_number.txt", "r")
        data = src.read()
    finally:
        src.close()
    primelist = data.split()
    sum = 0
    for i in range(0, num):
        sum += int(primelist[i])
    print("Sum is {}.".format(sum))
    data = {"answer": sum}
    req2 = requests.post(url, data=data, cookies=tmpcookies)
    print(req2.text)
    endtime=time.clock()
    print endtime - starttime

if __name__ == "__main__":
    main()

也可以将两部分写在一起

import requests
import re
import math

def prime_generate(n):
    result = list()
    result.append(2)
    result.append(3)
    for i in xrange(5,n+1,2):
        for j in xrange(3,int(math.sqrt(i))+1):
            if i%j == 0:
                break
        else:
            result.append(i)
    return result

def calc_sum(num):
    finsum=0
    for x in prime_generate(10000)[:num]:
        finsum=finsum+x
    return finsum  

def main():
    url = "http://hack.bckdr.in/2013-MISC-75/misc75.php"
    req = requests.get(url)
    tmpcookies = req.cookies
    # Set rundom N.
    match = re.findall(r'[0-9]+', req.text); num = int(match[1])
    sum=calc_sum(num)
    data = {"answer": sum}
    req2 = requests.post(url, data=data, cookies=tmpcookies)
    print(req2.text)

if __name__ == "__main__":
    main()

小伙伴有什么优化的算法还请告诉我，一起交流学习:P