6/15: Problematic Prime Numbers


#1

I cannot figure out how to make a checker for prime numbers, is it possible someone can explain to me step by step on how to do so and why it works, please? Here is my current code

def is_prime(x):
    for n in (2:x-1):
        if x%n:
            return False
        else:
            return True

#2

Ok, so a prime number is a number that

  1. Is Divisible by 1
  2. Divisible only by it's self

So how do we go about checking this, well let's start by ensuring that the number is greater than 1. Then we should see if the number is 2, then we check to see if the number is divisible by 2. Once that is done let's check all odd numbers between 3 and it's self divided by 2. We do not have to check anything over half for obvious reasons.

EDIT: START

  1. Is greater than 1
  2. Is 2
  3. Is divisible by 2
  4. Check all odd numbers from 3 to number divided by 2

EDIT: END
Ok let's program that.

def is_prime(int_):
    if int_ > 1:
        if int_ == 2:
            return True
        if int_ % 2 == 0:
            return False
        for test in range(3, int(int_ / 2), 2):
            if int_ % test == 0:
                return False
        return True
    return False

There we go that should do it.


#3

We really only need to check up to the square root of the number, not the half-way point.


#4

It's true but I didn't feel like explaining why. That is a topic in and of it's self.


#5

And neither did the course author, it would appear.

  1 * 100
  2 *  50
  4 *  25
  5 *  20
 10 *  10   #   cross-over point
 20 *   5
 25 *   4
 50 *   2
100 *   1

The above is one way of showing it. You're right, though. It will take some more explaining, and if math is not one's strong suit, ...


#6

Thanks for mentioning the square root bit because I did not get why we should have done 3/(int/2)


#7

What is the last 2 for? and also thanks a lot!


#8

It's called the stride, when you use it, it moves that any iterations each time. So in this case because I started at 3 it would go

3, 5, 7, 9, 11, 13, 15

Or counting odd numbers.


#9

We do not have to check anything over half for obvious reasons.

can you explain what the obvious reasons are?

the program is still successful if i run

for p in range(3, x, 2):
    if x % p == 0:
        return False

Sorry if my formatting is wrong. I don't know how to write code on this forum.


#10

Nothing over 1/2 of a number can be evenly divisible into said number, you can actually say that if the number is not 2/3 then nothing greater than 1/3 of the number needs to be calculated.After all 2 and 3 are the lowest prime numbers.

Does that make sense? You can actually just divide the number by the 100 lowest primes and then move on from there up-to 1/3 or the square root of the number. It would be faster for certain calculations but it does not really matter.


#11

so if i understand this right the above code written by flippin_lekker will run with x in the range rather then x/2 but it is simply faster and unnecessary to use the entire range of possibilities?


#12

Much faster to limit the range of possibilities to those that are proven necessary, yes. We can reason that. Technically, if we have a list of primes only, say 100 of them, we can derive all the primes up to roughly (primes sub100) ** 2.

This list of 100 primes makes up the modulus in our evaluations. We can again reason how this would shave off a tremendous amount of benchmark time.


6/15 is_prime code doesn't works