PmP: 6/15 - is_prime - This works but can it be 'better'?


#1

Hello again (multiple posts today as I’m really trying to make sure I am taking everything in…)

I have “solved” the is_prime challenge with the following code but I am curious if this is the ‘best’ way to find out if a number is indeed prime? For the sake of neatness I have stripped out user entries and call’s to the function and have only listed the base code in the is_prime function.

1. def is_prime(x):
2.     # if a number is less than two it is not Prime
3.     if x < 2:
4.         return False
5.     # if 2 is selected this is a Prime
6.     if x == 2:
7.         return True
8.     # does any previous integer in the range divide evenly into 'x'
9.     for i in range(2,x):
10.         if x % i == 0:
11.             return False
12.     return True

I would welcome more experienced users thoughts on other ways to implement this functions.
Cheers
L


#2

The most obvious optimisation here comes from making the observation that if you (for a non-prime) write down the numbers you successfully divide by, and the results, after you’ve found half the divisors the rest of them will be the results you already computed, and you therefore can stop at that point - there’s nothing more to find, you’ll only get the same numbers again.

divisors and quotients of 60
 2,  3,  4,  5,  6, 10, 12, 15, 20, 30
30, 20, 15, 12, 10,  6,  5,  4,  3,  2
    can stop here  ^

If you want to try other numbers than 60:

n = 3 * 4 * 5 * 6
print('divisors and quotients of {}'.format(n))

divisors = []
quotients = []

for divisor in range(2, n):
    if n % divisor == 0:
        divisors.append(divisor)
        quotients.append(n // divisor)


maxwidth = len(str(max(divisors + quotients)))
divisors = ', '.join('{0:>{1}}'.format(n, maxwidth)
                     for n in divisors)
quotients = ', '.join('{0:>{1}}'.format(n, maxwidth)
                      for n in quotients)

print(divisors)
print(quotients)

Beyond that, it gets rather advanced


#3

Blockquote
Beyond that, it gets rather advanced

Thank you @ionatan this looks plenty advanced to me :wink: I’ll have to go and play with your code and see if I can work out what it’s doing. Really appreciate you taking the time to reply.

I feel a “google search” session coming lol


#4

It prints the output shown in the box above it in my post

The second half may use some fancy features you haven’t yet learned but it’s merely string formatting to get the numbers to match up (by padding with spaces)

(find the largest number,
get its length as a string,
pad all numbers to that same width while converting them to string,
put ', ' between them.)

Really, ignore what that code is doing. It’s the output that’s interesting for your problem. You see me pointing out where you can stop, but I haven’t said how you’d know when you are at or past that point (see if you can figure that out. doing the numbers manually may make it much easier because it makes you go through the process instead of looking at the result)

Or, just take note of that, yes, there is a point where one could stop early. There’s nothing saying you actually need to do it.


#5

Thanks @ionatan its very kind of you to explain this. I’n very grateful for the support :smiley:


#6

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.