Practice Makes Perfect 6/15 what am I doing wrong?


#21

Yes, you’re right in how the different upper limits would affect the output from the range function. However, from a mathematical standpoint, in this example not dividing 10 by 9 to see if it goes evenly won’t impact the outcome of your function.

In practice, we don’t really need to bother with any divisors which are more than halfway between 2 and x.

If we consider again my example where x = 763, then to determine if this is prime we need to divide it by every positive integer between 2 and 762 to see if any of them go evenly, right? Wrong.

All prime numbers are a subset of another collection of numbers called natural numbers, and the set of natural numbers covers every positive integer value. So, 7, 6, and 3 are natural numbers; -2, -12 are not; and, just to be awkward, we can choose whether or not we want to include 0 as part of the set.

We can therefore redefine prime numbers in terms of natural numbers: a prime number is a natural number that cannot be formed by multiplying two smaller natural numbers.

From this definition, we know that all of our divisors must be natural numbers - that is to say integers - and so we can’t do 763 / 6.104 = 125 and use that to rule out 763 as a prime, as 6.104 is not a natural number.

When we’re checking whether x is prime, the smallest natural number that we need to check is 2 so we do 763 / 2 = 381.5. From this we also know that 763 / 381.5 = 2.

What we know from this is that if we divide x by any number larger than the halfway point - in this case 381.5 - we are going to get an answer that is somewhere in between 1 and 2. (e.g. 763 / 382 = 1.997382).

The point of our function is to see whether x / n produces an integer output. If we know that any value of n larger than x / 2 will never produce an integer output, because it’ll be “one and a bit” as shown above, then why bother calculating them? :slight_smile:

Hopefully that makes sense. Yay for math!


#22

Oooh so when we pass halfway through the numbers there is no need to divide x by the rest of the numbers…I didn’t know that. Now it makes sense why x-1 would work :wink: Thank you again for the explanation!


#23

What I’ve been saying all along.

def is_prime(x):
        if x > 2:
            for n in [2] + list(range(3, int(x ** 0.5 + 1), 2)):
                if x % n: continue
                return False
        return x > 1

When x is 9199, this is the list of test candidates…

[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 
31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 
59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 
87, 89, 91, 93, 95]

When we get right down to it, we only need to test with the primes from that list…

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89]

Why does is_prime fail for some numbers?
#24

Oh ok, then I’ve misunderstood…

But wouldn’t the list of candidates be up to 4599, you know since its the halfway number…?


#25

Not when we get down to the nitty gritty. That a candidate being higher than the halfway point is moot, goes without saying, but why go all the way to half when the square root is high enough?

The only real point worth making here is that whatever the lesson gives, (2, x) or (2, x - 1), it doesn’t matter. That’s the point that should have been stressed from the beginning, but the author didn’t want to open up too many questions, one supposes. Little did he know this would be a giant burr under the saddle of many learners.

It never occured to the author that a good many learners will not have the requisite math understanding to know what a Prime number is, let alone how to construct an algorithm to test if a number is prime or not.

To my mind this exercise (the whole PMP unit) is very poorly timed and should not have been inserted into the track until after all the core concepts were already covered, and somewhere in the course a sample could have been introduced that demonstrates the basic brute force algorithm that is implied in this exercise.


#26

Oh ok so the numbers up to the squareroot number of x is enough, I’ll remember that!

AMEN TO THAT!!! Cant understand why they dont do something about it!


#27

Let’s look at 121, for example.

121 ** 0.5 => 11

Dividing 121 by [2,…11] will be enough to learn that it is factorable. We don’t need to know the other factors (though it in this case the only other factor is 11).

Once we root out the largest of the small factors we come to a cross-over. As the one factor grows larger, the other grows smaller.

2, 4, 5, 10, 20, 25, 50

are all factors of 100. But we only need 2, 4, 5, 10 to find all the others.


#28

Having done the Python track, I don’t think there’s anything in Practice Makes Perfect that requires the use of a programming structure not already introduced prior to the lesson. What you can’t account for is how much time the learner has spent getting familiar with the previously introduced structures, or their ability to apply them to a problem with less guidance than before.

When I was completing the Python course, PMP struck me as a gate of sorts to determine how much of the previous material had stuck and how well you could recall and apply it. Difficulty here would, to me, suggest that one ought to review the previous topics until you can solve the exercises.

Whether or not the learner has the math skills necessary to do things like the is_prime exercise is a separate question…


#29

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