6. is_prime what is wrong in the code?


#1


return False

Oops, try again. Your function fails on is_prime(9). It returns True when it should return False.

what is wrong here??


#2

So, if you follow closely with your code, you have to keep in mind that for-loop will never stop until it goes through all the numbers within the range set. Having said that, even if one of the numbers returned False, it will keep on going until it reaches the end, and it might return True for that very last number. For a number like 9, what the code does is it will return False at 3, but it will keep on running, and when it reaches 8, it will return True. So what do you do? I will leave that for you to answer.


#3

That is questionable. How can a loop keep running when the function has been exited?


#4

I'm Vietnamese. I'm not good English, so I will try explain my code if you need your answer.
This is my code. It worked.


#5

The OP is not responding to replies so we can probably consider this an abandoned thread. Your reply may go unnoticed. We are asked in the forum guidelines to not post complete solutions without some meaningful explanation, and we should try to focus on the OP code in our working model. Providing something to compare to is okay, when it is in this context.

That said, we can examine your solution, which is quite clever.

def is_prime(x):
    if x > 2:
        a = []
        m = 1
        for n in range(x-2):
            m += 1
            ans = x % m
            a.append(ans)
        return False if 0 in a else True
    return True if x == 2 else False

I've refined it slightly with Python ternaries. Always love getting a chance to practice with those.


#6

Tks :smiley: Nice to meet you. I've optimized it. Looks less lines of code than.
But Moderator request me do not post answers, it is not according to the guide-lines. But we can discuss through messages


#7

in my case.. :slightly_smiling:


#8

Do you mean,

    if x < i:
        return False

? If x == i it returns True. That is clever.

Very sparse, and to the point. Nice one. Its work load could be cut by more than half if the sample space is 0.5 * x or x ** 0.5. Nothing over half of x can be divided into it, and factors can be determined with the square root of x, plus 1 as the upper bound of the modulo.


#9

oops. that's right.
if x < 1: --> this is correct.


#10

Do you mean x < i as in 'ex' less than 'eye'? I'm content with it being i not 1 and the logic makes perfect sense.

This is blisteringly fast.

 > is_prime(1023043053073093)
=> False

instantly.


#11
Code
from math import floor, sqrt

def is_prime(x):
    i = 2
    if x < i:
        return False
    u = floor(sqrt(x)) + 1
    while i < u:
        if x % i == 0:
            return False
        else:
            i += 1
    return True
from math import floor, sqrt

def is_prime(x):
    i = 2
    if x < i:
        return False
    u = floor(sqrt(x)) + 1
    while i < u:
        if x % i == 0:
            return False
        else:
            i += 1
    return True

#13

A lot more speed is gained, in my view. There are a fraction as many iterations and modulo computations. The square root of a million is a thousand. How many less iterations is that?


#14

By the time we do the modulo of all the numbers less than the square root, we will have found all the factors greater than the square root. To go any further is a waste.


#15

if x < i: is right. :slightly_smiling:

and..

do u mean that root of x make more faster, right?


#16

See the above post. There is link to the lab (This).

We can see how fast yours was. This is theoretically much faster. It uses so little resources and runs a fraction as long. The real gains are on very large numbers.


#17

What about getting rid of the even divisors? Would it improve the performance?

def is_prime(x):
    if x < 2:
        return False
    else:
        y = 2
        while y < x:
            if x % y == 0:
                return False
                break
            else:
                if y == 2:
                    y += 1
                else:
                    y += 2
            
        return True

#18

Yes it would. I'll revise my earlier code to reflect that...

from math import floor, sqrt

def is_prime(x):
    i = 2
    if x < i:
        return False
    elif x > i and x % i == 0:
        return False
    u = floor(sqrt(x)) + 1
    while i < u:
        if x % i == 0:
            return False
        else:
            i += 2
    return True

#19

break after return is unreachable and not needed.


#20

There are so many ways to test primeness we will never see them all, most likely. Typically, we reach for brute force solutions such as we have above. Some other approaches that are more theoretical (and go over my head) are out there in the world of advanced mathematics, to be sure.

One such approach uses an algorithm to generate pairs of numbers derived from the input, let's call it n. I found the following in a discussion over here: Prime numbers and twins.

Given,

6 * (n - m) + (m + 5)
and
6 * (n - m) + (m - 5)

as general forms of prime numbers, how might we construct the algo that builds a pairs list, then evaluates the GCD of each pair?

Witness the example given:

29 = 6(5) - 1 = 6(4) + 5 = 6(3) + 11 = 6(2) + 17 = 6(1) + 23

which resulted in this list of pairs:

  • (24, 5)
  • (18, 11)
  • (12, 17)
  • (6, 23)

Finding their GCD is no problem. We can write a simple recursive function for that:

def gcd(a,b):
    if a == 0:
        return b
    elif b == 0:
        return a
    elif a > b:
        return gcd(b, a % b)
    elif b > a:
        return gcd(a, b % a)

print (gcd(24,5))      # 1  
print (gcd(18,11))     # 1  
print (gcd(12,17))     # 1  
print (gcd(6,23))      # 1

Our algo wouldn't have to build a complete list of pairs, just until it finds a pair whose GCD is not 1. I've been trying to wrap my head around this for some time, now, and keep coming back to it. If anybody has some insight into how we might build the algo, I'm all ears.


#21

Awesome research!

But as you said, this kind of solutions are way beyond my very limited maths knowledge. Too bad.

Anyway, I'm just happy, because I could figure out a solution, even if it's kind of primitive. XD

Thanks for the help!