# Find the kth prime and all the primes below it

It works by finding 2n+1 with n from 1 to k, but not where 2n+1 would be divisible by one of the already known primes. I'd like to know if the program can find every prime, and if so, how it compares to the efficiency of other algorithms.

n=1
k=input()
primes=[2]
def f(n):
b, a = 1, 1
for i in primes:
a=((2*n+1)%i)
b=b*a
return b
while k > n:
if f(n) >= 1:
primes.append((2*n)+1)
n=n+1
else:
n=n+1
k=k+1
print primes


Before we talk about efficiency, let's talk about something very important: readability. It took me an unreasonably long time to understand what it was your code was doing, due to lots of single-letter variable names, confusing flow control, and odd choices for functions.

Checking for primality

Let's start with f. f is apparently determining the primality of n, so let's call it is_prime. Furthermore, it's not actually determining the primality of n, it's determining the primality of 2n+1. That's too much for one function - let's change it's responsibility to take the number it tests. The way you're doing it (taking the % against every prime) is a good algorithm, but then you're multiplying the mods together. That doesn't make sense as an operation. You don't care about the product, you care if any of them are zero! And as soon as one of them is zero, you can return False.

Here's a clearer function:

def is_prime(n):
for p in primes:
if n%p == 0:
return False
return True


Or if you're generator inclined:

def is_prime(n):
return not any(n%p == 0 for p in primes)


Main Loop

We need to find k primes. You are keeping track of this by comparing k to n and occasionally incrementing k. That is confusing. Since we're already keeping track of all the primes, the termination condition should be:

len(primes) >= k


And then we can handle iteration by the odd numbers with itertools.count():

num_primes = input()
primes = [2]

def is_prime(n): ...

for n in itertools.count(start=3, step=2):
if is_prime(n):
primes.append(n)

if len(primes) >= num_primes:
break


This program is far easier to understand.

Efficiency

We could do better in terms of efficiency. At a first approach, we're checking all the odd numbers but we can drop the multiples of 3 earlier by simply writing our own generator that spits out 3, 5, and then alternates adding 2 and 4. That's a quick optimization that let's us keep the same algorithm.

Better would be to use an entirely different, and very well-known algorithm: the Sieve of Eratosthenes. It is a much better algorithm for this problem.