There is an error in section b:
since k is always even (except for the first iteration), the running time of trial_division is always O(1) (think why). In the first iteration, trial_division also runs in O(1). Therefore, the total running time is simply the amount of iteration, which is O(log(num)) = O(n). So, the hints given in this section are not relevant.
Here is what we are going to do: section b (and only this section) is turned into a bonus of 10 points, with the following change: instead of k*=2 in the last line of foo(), we increase k this way:
k = 2*k+1
An updated version of HW3 was uploaded.