Basic prime number generator in Python

Question

Just wanted some feedback on my prime number generator. e.g. is it ok, does it use to much resources etc. It uses no libraries, it's fairly simple, and it is a reflection of my current state of programming skills, so don't hold back as I want to learn.

def prime_gen(n):

    primes = [2]
    a = 2 

    while a < n:

        counter = 0 

        for i in primes:
            if a % i == 0:
                counter += 1

        if counter == 0:
            primes.append(a)
        else:
            counter = 0

        a = a + 1

    print primes

Answer 1

I made improvements on the solution proposed my jimifiki

import math #for finding the sqare root of the candidate number
def primes(n):
  test = [3] #list of primes new candidates are tested against
  found = [5] #list of found primes, which are not being tested against
  c = 5 #candidate number, starting at five
  while c < n: #upper bound, largest candidate will be this or 1 bigger
    p = True #notes the possibility of c to be prime
    c += 2 #increase candidate by 2, avoiding all even numbers
    for a in test: #for each item in test
        if c % a == 0: #check if candidate is divisible
            p = False #since divisible cannot be prime
            break #since divisible no need to continue checking
    if p: #true only if not divisible
        if found[0] > math.sqrt(c): #is samallest in found > sqrt of c
            found.append(c) #if so c is a prime, add it to the list
        else: #if not, it's equal and we need to start checking for it
            test.append(found.pop(0)) #move pos 0 of found to last in test
  return([2] + test + found) #after reaching limit returns 2 and both lists

The biggest improvement is not checking for even numbers and checking the square root only if the number is not divisible, the latter really adds up when numbers get bigger. The reason we don't need to check for the square root is, that the test list only contains numbers smaller than the square root. This is because we add the next number only when we get to the first non-prime not divisible by any of the numbers in test. This number is always the square of the next biggest prime which is also the smallest number in found. The use of the boolean "p" feels kind of spaghetty to me so there might be room for improvement.

Answer 2

Here is the standard method of generating primes adapted from the C# version at: Most Elegant Way to Generate Prime Number

def prime_gen(n):

    primes = [2]

    # start at 3 because 2 is already in the list
    nextPrime = 3

    while nextPrime < n:

        isPrime = True

        i = 0

        # the optimization here is that you're checking from
        # the number in the prime list to the square root of
        # the number you're testing for primality
        squareRoot = int(nextPrime ** .5)

        while primes[i] <= squareRoot:

            if nextPrime % primes[i] == 0:

                isPrime = False

            i += 1

        if isPrime:

            primes.append(nextPrime)

        # only checking for odd numbers so add 2
        nextPrime += 2

    print primes