code: def gries_misra(n):
      
      primes = []
      factor = [0] * n
      for x in range(2, n):
          if not factor[x]:     # no factor found
              factor[x] = x     # meaning x is prime
              primes.append(x)
          for p in primes:      # loop over all non primes of the form p * x
              if p > factor[x] or p * x >= n:
                  break
              factor[p * x] = p
      return primes, factor
docs: Prime numbers by the sieve of Gries-Misra
      Computes both the list of all prime numbers less than n,
      and a table mapping every integer 2 ≤ x < n to its smallest prime factor
  
      :param n: positive integer
      :returns: list of prime numbers, and list of prime factors
      :complexity: O(n)