Shortest prime number generator we could come up with? I worked with a friend on the following prime number generator. Our goal was to make it as short and as fast as possible. This is what we came up with:

def p(n): # will print out primes between 0 and n
  s=[True]*(n/2)
  for i in range(int((n/2-1)/2) &gt;&gt; 1):
    for j in range((i*(i+3)&lt;&lt;1)+3,n/2,(i&lt;&lt;1)+3): s[j]=False
  return [2] + [((i&lt;&lt;1)+3) for i in range(n/2) if (s[i])]
print p(input()) # input number for n


Can it be made any faster? Also, it crashes due to memory errors if numbers larger than 1010 are inputted. Can this be fixed to make it more memory efficient?
0. Quick comments on your code


Clearer function names and
variables in your code. What does p mean, and what is s? I can
guess, but please.
Include a docstring or some indication of what your code does
Use the  if __name__ == "__main__": module. 


I did some quick speed comparisons of your function which you can see below. 

magic1            21.9095528103 ms
magic2            26.5589244423 ms
Joseph Farah    1030.95786404   ms


I did 10 runs with primes up to \$2\$ million. Now note the big gap between the optimized functions and yours. Even if you were to speed up your code tenfold you would still be 10 times slower than the other functions. 


  You can add as many horses you want to your cart, but it will never beat a ferrari.


With this in mind i propose three solutions


Implement a better algorithm
Use Import 
Give up


1. New algorithm

Wikipedia can shed some light on how to find larger primes.


  For the large primes used in cryptography, it is usual to use a
  modified form of sieving: a randomly chosen range of odd numbers of
  the desired size is sieved against a number of relatively small primes
  (typically all primes less than \$65,000\$). The remaining candidate
  primes are tested in random order with a standard probabilistic
  primality test such as the Baillie-PSW primality test or the
  Miller-Rabin primality test for probable primes.


So in short you use for an example Wheel factorization to find possible primes, then use the Rabin_primality_test to test whether the candidates are primes. Without going too technical the Rabin_primality_test is a probabilistic test. If the function returns True p might be prime, if False we are guaranteed it is not. If n is composite then the Miller–Rabin primality test declares n probably prime with a probability at most \$4^{−k}\$. A friend told me banks used tested primes 80 times. The chances of a composite number passing \$80\$ tests is \$4^{-80}\$ which is in incredibly low number. 

A comparison of many different sieves and ways to find primes can be found here https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n. I used the fastest one on my machine primesfrom2to to generate the results above

import numpy as np
def magic1(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n&gt;=6, Returns a array of primes, 2 &lt;= p &lt; n """
    sieve = np.ones(n/3 + (n%6==2), dtype=np.bool)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      ((k*k)/3)      ::2*k] = False
            sieve[(k*k+4*k-2*k*(i&amp;1))/3::2*k] = False
    return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]


2. Use Import



Python is magical in the sense that you can find libaries which pretty much do anything. The best part is that installing new packages is easy as \$\pi\$. There are many libaries for primes, I will mention a few below


primesieve
primefac
pyprimesieve


primesieve] is Python bindings for the primesieve C++ library. It can generate list of primes at an incredible speed, and also has fast nthprime implementation. primefac is incredibly good at factoring primes, it can also generate primes, but is rather slow. pyprimesieve 
has functions such as prime_sum and has many nifty specialized functions. 

So if you want a golfed answer the best you can get in terms of speed is

from primesieve import generate_primes

if __name__ == '__main__':

    print generate_primes(2*10**6)


3. Give up

Even if you are in your prime finding and generating large primes are incredibly hard. However this is a good thing as primes are incredibly important in internet security. If by some miracle you were to find an incredibly, incredibly fast prime generator it would break all the large banks and make payments over the net unsafe. 

So perhaps it is a good thing your code is slow ;)