squares.py

#!/usr/bin/python3
from math import sqrt, log
from sys import argv

N = int(argv[1])

primes = list()
for i in range(2, int(sqrt(N + 1))):
  if not any(i % p == 0 for p in primes):
    primes.append(i)

powers = list()
for p in primes:
  maxpow = int(log(N + 1, p))
  pows = [p ** e for e in range(maxpow + 1) if e != 1]
  powers.append(pows)

def rec(maxval, ret, pidx, prod):
  if pidx == len(powers): # No more primes!
    ret.append(prod)
    return
  
  pows = powers[pidx]
  for i, v in enumerate(pows):
    if prod * v > maxval:
      break
    rec(maxval, ret, pidx + 1, prod * v)

ret = list()
rec(N, ret, 0, 1)
print(ret)

squares_iterative.py

#!/usr/bin/python3
from math import sqrt, log
import sys

class PrimeSquares(object):
  @staticmethod
  def primes(n):
    primes = list()
    for i in range(2, int(sqrt(n + 1))):
      if not any(i % p == 0 for p in primes):
        primes.append(i)
    return primes

  @staticmethod
  def prime_powers(n):
    powers = list()
    for p in PrimeSquares.primes(n):
      maxpow = int(log(n + 1, p))
      pows = [p ** e for e in range(maxpow + 1) if e != 1]
      powers.append(pows)
    return powers
  
  class Entry(object):
    __slots__ = ['prod', 'idx']
    def __init__(self, prod = 1):
      self.prod = prod
      self.idx = 0
  
  def __init__(self, n):
    self.n = n
    self.powers = PrimeSquares.prime_powers(n)
  
  def _iterate(self):
    # If no more primes, return a result
    cur = self.stack[-1]    
    if len(self.stack) > len(self.powers):
      self.stack.pop()
      return cur.prod
    
    # Are we out of powers for the current prime?
    pows = self.powers[len(self.stack) - 1]
    if cur.idx == len(pows):
      self.stack.pop() # Go back to the previous prime
      return
    
    # Is our next power too high?
    next_prod = cur.prod * pows[cur.idx]    
    if next_prod > self.n:
      self.stack.pop()
      return
    
    # Continue with our next power
    self.stack.append(PrimeSquares.Entry(prod = next_prod))
    cur.idx += 1
  
  def __iter__(self):
    self.stack = [PrimeSquares.Entry()]
    while self.stack:
      v = self._iterate()
      if v != None:
        yield v
    
n = int(sys.argv[1])
print(len(list(PrimeSquares(n))))

Usage:

$ ./squares.py 200
[1, 169, 121, 49, 25, 125, 9, 27, 81, 4, 196, 100, 36, 108, 8, 200, 72, 16, 144, 32, 64, 128]