Programación (II): Solución Reto CTFLearn "Can your memory handle prime numbers?"

En este post la solución a otro de los retos de programación de la plataforma CTFLearn.

Este reto tiene el título "Can your memory handle prime numbers?" y mi valoración sobre su dificultad es: ★★★☆☆.

Su enunciado dice lo siguiente:

How many prime numbers are smaller than 987163160? Give the answer in base64 format.

Flag: CTF{number_in_base64_format}.

Solución: utilizo el siguiente script de Python.

from time import time

def buscar_primos(num_max):
      global primos, tot_primos
      primos = [2]
      tot_primos = 1
      i = 3
      while i <= num_max:
             es_primo = True
             sqrt = int(i**(0.5) + 1)
             for primo in primos:
                   if i%primo == 0:
                           es_primo = False
                           break
                   if primo >= sqrt:
                           break
             if es_primo:
                   primos.append(i)
                   tot_primos = tot_primos + 1
             i = i+2
      return primos, tot_primos

num_max = int(input('Introduzca el numero del que hay que buscar numeros primos menores que el ... : '))
tiempo_inicial = time()
buscar_primos(num_max)
print""
print "Total de numeros primos hasta el numero", num_max, "...", tot_primos

tiempo_final = time()
tiempo_ejecucion = tiempo_final - tiempo_inicial
print 'Tiempo de ejecucion en segundos:',tiempo_ejecucion

Y tras ejecutar este script, tras aproximadamente 6.985,06599998 segundos (1 h:56 m:25 s; duración que lógicamente depende del equipo empleado, pero que ya nos indica que no es un algoritmo precisamente muy eficiente), obtengo que el total de números primos menores que 987.163.160 es de 50.227.870:

Codifico ese número en base 64:  NTAyMjc4NzA=, y esa cadena es la solución del reto, es decir, CTF{NTAyMjc4NzA=}.