This one is using Python to check for prime numbers from 2 up to whatever value we have chosen. In this example, it is up to 50, but you can choose whichever value you wish.

This is using Python 3.

If you're transitioning from Python 2 you can use this acronym to remember the basic differences.

DRIP

Division is true division 2/3 = 1.5

Range is a generator, and there is no more xrange.

Items will help you get to Dictionary elements, you do not need iteritems

Print() is a function and no longer a statement. you need those parens

if you want to not print a newline,

instead of a comma, you need to use end="" You can put a character in the ""

## Prime Number Checker

max = 51

print ("Prime numbers up to", max)

for i in range(2,max):

#skip evens

if i % 2 == 0:

# 2 is our first prime number, print it out

if i == 2:

print (i, end=" ")

continue

# check each value is divisible by 3 up to the value being checked

# we don't need to check using 2 because we already excluded the even numbers above

evennum=False

for k in range (3,i):

if i % k == 0:

evennum=True

break

if evennum==True:

continue

else:

print(i,end=" ")

But wait~ There's more.

If a number is not prime then it has factors and for each two factors, one of them is below the square-root of the value you are checking. We only care if one of the factors exists (which will make the value not prime. As a result, we only have to check the values up to the "floor" (truncated integer) of the square-root of the value we're checking.

Example. Let's look at 36 which is not prime (we'll ignore that it's an even number and won't ever show up on our list.

sqrt(36) = 6

36 has other factors

2x18

3x12

4x9

If we find even one of these factors we know it's not prime.

See how the factors distribute themselves around the squart-root

One is always lower and the other is always higher than 6.

So instead of for k in range (3, i)

we can do for k in range(3, math.floor(math.sqrt(i))

Since we're now doing math functions, we need to include the math module.

Here is a good reference (scroll down):

http://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr

Here's the full code:

import math

max = 51

print ("Prime numbers up to", max)

for i in range(2,max):

#skip evens

if i % 2 == 0:

# 2 is our first prime number, print it out

if i == 2:

print (i, end=" ")

continue

# check each value is divisible by 3 up to the value being checked

# we don't need to check using 2 because we already excluded the even numbers above

# NOTE we only need to check if there's a factor up to the square-root of the series

# (See the text for an explanation)

endval = math.floor(math.sqrt(i))

evennum=False

for k in range (3,endval):

if i % k == 0:

evennum=True

break

if evennum==True:

continue

else:

print(i,end=" ")

## No comments:

Post a Comment