1
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. This is was one of the first programs I made, and I was unsure about a lot of things, but your response was very helpful. \$\endgroup\$ – nousernameplease Oct 17 '15 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.