Python 3, 117 bytes
===
This solution is slightly trivial, as it outputs 0 where a number is not prime, but I'll post it anyway:

    r=range
    for i in [2]+[0 if 0 in [i%j for j in r(3,int(i**0.5)+1,2)] else i for i in r(3,int(input()),2)]:
	    print(i)
Also, I'm not sure how to work out the complexity of an algorithm. Please don't downvote because of this. Instead, be nice and comment how I could work it out. Also, tell me how I could shorten this.