8
\$\begingroup\$

The program is to get the nearest prime number to a number while adding a number. I solved the problem but I wish to optimize the code.

import time
def isprime(a ,d):
    b=a
    c=0
    f=b**(0.5)
    for i in range(1,int(f)+1):
        if a%i==0 and c<=1:
            c+=1
    if c==1:
        return d.append(b)
    else:
        b=a+1
        isprime(b,d)
 
start=time.time()        
b=[89, 54,36, 74, 44, 19, 12]   # Input
d=[]
for i in b:
    isprime(i,d)     #function call
print(d)             #output is [89, 59, 37, 79, 47, 19, 13]
stop=time.time()
print(stop-start)    #0.0001347064971923828 Seconds

Help with Code optimization. I'm just a beginner I know code is of lower. Help to learn bit of coding.

\$\endgroup\$
3
  • \$\begingroup\$ Sympy has a nextprime, which practically does what’s in the title of your question. \$\endgroup\$
    – agtoever
    Jun 19 '20 at 21:40
  • \$\begingroup\$ @Graipher I don't want a nearest prime. I want which number is add to get a prime \$\endgroup\$
    – Deepan
    Jun 20 '20 at 4:15
  • \$\begingroup\$ @Deepan Then you should edit your question and change your explanation. \$\endgroup\$
    – Graipher
    Jun 20 '20 at 5:12
6
\$\begingroup\$

To be cheeky, the ultimate optimization is "don't use Python for numerics", and the next-best optimization is "use a library rather than writing this yourself".

It's worth having a read through https://stackoverflow.com/questions/4114167/checking-if-a-number-is-a-prime-number-in-python

Also consider calling into https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.primetest.isprime .

Otherwise:

Roots

I do not trust Python to do the right thing here:

b**(0.5)

Just call isqrt instead, which will be more likely to get an optimized implementation. This is confirmed here: https://stackoverflow.com/questions/327002/which-is-faster-in-python-x-5-or-math-sqrtx

Variable names

You need to get out of the habit of single-letter variable names. I have no idea what b means other than inferring based on context.

Time measurement

Use timeit. Your current implementation only has a single iteration for each of the input values and is thus extremely vulnerable to CPU thread-switching noise, etc.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Actually, isqrt(x) is the function you want to use. It remains accurate even when the input exceeds the value which can be accurately represented in a float. \$\endgroup\$
    – AJNeufeld
    Jun 20 '20 at 4:50
  • \$\begingroup\$ Single letter variable names are not a bad habit. I'd much rather see a for loop indexed with "i" than something stupid like "l_loop_index". Similarly, temporary computation variables are perfectly fine to be called a,b,x,y,... \$\endgroup\$ Jun 20 '20 at 10:11
  • \$\begingroup\$ @CaptainCodeman I disagree, and i_loop_index is a poor counter-example, because it's just as meaningless as i. Given the choice between (say) i and factor_index I would prefer the latter every time. \$\endgroup\$
    – Reinderien
    Jun 21 '20 at 2:25
  • \$\begingroup\$ @Reinderien If you cannot keep track of abstract concepts like "i" you have no business in software development. Try a career in teaching. \$\endgroup\$ Jun 22 '20 at 9:37
4
\$\begingroup\$

First, some comments on your code:

  • return d.append(b) is not very nice. You would think this function actually returns something, but this just returns None. Instead you modify a list being passed in as a parameter. This is a very C thing to do. Instead, just return the boolean value and use it to build a list using a list comprehension:

     d = [x for x in b if isprime(x)]
    
  • Note that this now no longer solves the problem. That is because your naming should be improved. The isprime function does not actually check if a number is prime. It does that somewhere in its implementation, but that is not what it really does. I would rename the function to something like nearest_prime. You should also try to avoid single letter variable names. A few exceptions like integers called i might exist, but not too many.

  • You also generally want to avoid writing recursive functions in Python. Python has a maximum recursion limit, it does not do tail call optimization. Instead make your function iterative.

  • Python has an official style-guide, PEP8. It recommends using spaces around = when using it for assignment.

  • You should always add a docstring to your functions.


This part of the answer assumes that you want what is written in your title, and not what is written in the question. The number you want is the next larger prime, unless the number is prime itself.

In any case, you can greatly speed up your code by pre-computing the primes. This will be only really worth it if you query enough numbers.

For getting lots of prime numbers fast, you want to use a prime sieve. Here is the most simple one, the Sieve of Eratosthenes:

def prime_sieve(limit):
    """Generator that yields all prime number up to `limit`."""
    prime = [True] * limit
    prime[0] = prime[1] = False

    for i, is_prime in enumerate(prime):
        if is_prime:
            yield i
            for n in range(i * i, limit, i):
                prime[n] = False

The hard part is then knowing up to which number to get the primes. I'm going to ignore this and just use a large enough number (since I know all numbers you are going to test). In your code you might want to automate finding that number.

For finding the next bigger prime, or the number itself, we just have to look in the list of primes until we either find our number or a number that is bigger than our number. We could do a linear search for it, but it will be faster to do a binary search (since the primes are already sorted). For this you can use the bisect module, which is in the standard library:

from bisect import bisect_left

def nearest_prime(x, primes):
    """Find the first prime number from `primes` greater or equal to `x`."""
    return primes[bisect_left(primes, x)]

And that's really already it. Just add your calling code under a if __name__ == "__main__": guard to allow importing from this module without the example code being run and you're done:

if __name__ == "__main__":
    primes = list(prime_sieve(100))
    numbers = [89, 54, 36, 74, 44, 19, 12]
    nearest_primes = [nearest_prime(x, primes) for x in numbers]
    print(nearest_primes)
    # [89, 59, 37, 79, 47, 19, 13]

On my machine, your code takes 0.00015s, while this takes 0.00004s. But as I said, this will be even faster the more numbers you check.


If you really do mean the nearest prime (so it can also be smaller), it takes only one extra step, we also need to check the prime number before the index we get:

def nearest_prime(x, primes):
    """Find the closest prime number to `x` in `primes`."""
    i = bisect_left(primes, x)
    return min(primes[i - 1], primes[i], key=lambda y: abs(x - y))
\$\endgroup\$
5
  • \$\begingroup\$ You also want to avoid writing recursive functions in Python - ish. This is a true statement only if it's qualified with for unbounded input . In some cases, where the maximum recursion depth is well-known, it's a good solution. \$\endgroup\$
    – Reinderien
    Jun 19 '20 at 18:56
  • 1
    \$\begingroup\$ @Reinderien: I agree -ish. First note that in this case the input is potentially unbounded. The gap between prime numbers increases, so eventually you will hit the stack limit. Although in practice the input is limited, which I have also used in my answer. But then I think while there are use cases where the input is bounded so you know it is less than the stack limit, most of the time it is still better to rewrite it iteratively. Once because IMO it is more readable (probably because I'm not used to recursive code) and then because it gets you into the habit of not writing recursive code. \$\endgroup\$
    – Graipher
    Jun 19 '20 at 19:13
  • \$\begingroup\$ Also because Python doesn't have tail recursion optimization. \$\endgroup\$
    – Reinderien
    Jun 19 '20 at 19:43
  • \$\begingroup\$ @Reinderien: Yes, that is the technical reason. \$\endgroup\$
    – Graipher
    Jun 19 '20 at 20:05
  • 1
    \$\begingroup\$ Thanks for your recommendations \$\endgroup\$
    – Deepan
    Jun 20 '20 at 14:16

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.