Prime numbers are important creatures.

They are the building blocks of the whole numbers, and are central to the

field known as Number Theory. Primes are also a key ingredient in some

cryptographic methods, like the RSA algorithm. But identifying prime numbers

is difficult. Today, we rise to the challenge and will

use Python to write a series of functions to check if an integer is

prime. I hope you’re ready for the main event, because it’s prime time. To begin, let’s recall the definition of a prime number. A prime number is a positive

integer that is divisible only by itself and 1. If an integer can be factored into

smaller numbers, we call it a composite number. And the integer 1 is neither

prime nor composite. It’s called the unit. For our first version of the function, we

will check all divisors from 2 through n minus 1. We skip 1 and n since every number

is divisible by itself and 1. Let’s call the function is prime V 1. And the input

will be our integer. First do the right thing, and write a brief docstring

describing this function. Next, loop over all numbers from 2 through n minus 1.

Remember, with the range function the last number is not included. 2 see if d

divides n evenly, we’ll use the percent operator. This gives you the remainder

when you divide n by D. If we get a remainder of 0, then n has a divisor

other than itself and 1, so it is not prime. But if at the end of the loop we

have not found a divisor, then n must be prime, so return true. Let’s test this on

the first 20 positive integers. Our function works. It correctly identifies

the prime numbers. But how fast is this function? Let’s find out by doing a

larger test. We’ll compute the time required to test the integers up to

100,000. To do so, import the time module and call the time function before and

after the loop. We won’t print out anything, because we’re interested in the

computation speed, not how fast our system can print text. I’m… disappointed. I think we can do

better. To improve our function, we will use a trick to reduce the number of

divisors in the for loop. To see the trick let’s look at all the ways we can

factor 36 as the product of two positive integers. We’ll arrange the product so

the first factor is always increasing, while the second factor is always

decreasing. 36 is a perfect square, since it’s equal to six times six.

Notice that the factorizations after this are the same as the factorizations

before it, just in reverse order. If the number is not a perfect square, that’s

okay. To see why, look at 18. Here, there are six products and the first three and

the last three are the same, just in reverse order. But the product of the

square root of 18 times the square root of 18 still provides a dividing line

between duplicate products. For any positive integer n, the same thing

happens. This means to test for divisors, you only have to test the integers up to

the square root of n. Let’s use this to improve our algorithm. For our second

version, we will only test divisors from 2 up to the square root of N. In the

event the square root is not a whole number, we’ll just round down. Since we’ll

be taking square roots we need to import the math module. To find the largest

possible divisor we’ll test, take the square root of n then round down using

the floor function. Since we want to be sure to test this number we have to add

one to the range function Let’s check that the function works. It does. Let’s see if it’s faster than the first . Once again, we’ll compute

the time required to test the integers up to 100,000 This is much much better. But I suspect there is still room for improvement. In our loop, we go over all

even integers up to the limit. This is a waste. If the input is even and

bigger than 2, we will find a divisor on the first step. But if the input is odd,

it’s a waste to check the even divisors. Let’s fix this in version 3 of our

function. The first thing we will do is check if n is even. We only do this for

integers larger than 2, since 2 is a prime number. If the input is larger than

2 and even then it cannot be prime. Next, when we range over the possible divisors,

we will add a third parameter: a step value. This range will start at 3, and

cover all odd numbers up to our limit. This should eliminate roughly half of

all division operations. Let’s now test and time this function. The test looks good. But how fast is it? roughly twice as fast as version two. I’m feeling some

kind of emotion Could it be joy? With just a few simple optimizations, we

were able to see dramatic improvements in performance in our prime testing

function. But what if you are working with extremely large integers? If you are

building or cracking codes, these functions aren’t nearly fast enough.

You will need to go deeper. After you subscribe to our channel, I would

encourage you to look into the subject of pseudo primes. In your excitement, you

may feel the need to visit our Patreon page. Don’t worry. This is a completely

normal reaction to one of our videos.

One more request ,Could you Please add some more videos for python libraries like numpy ,pandas also .Many Many Thanks again for this Socratica channel.

could've just used math.ceil instead of math.floor + 1

in version 3, there is no need to check if n > 2 since we already checked if n == 2

how does 'for d in range(2, 2)' return true? it looks like it should return false

your videos help me a lot in learning Python…i'd really appreciate if you make more videos like this.

aaaw <3

Never seen this superb way to teach awesome stuff

TypeError: range() integer end argument expected, got float.

code —>

import math

def is_prime(n):

if n==1:

return False

if n == 2:

return True

if n > 2 and n%2 == 0:

return False

max_divisor =math.floor(math.sqrt(n))

for d in range(3,1 + max_divisor , 2 ) :

if n % d == 0 :

return False

return True

for n in range(1,21):

print (n,is_prime(n))

A video on getters and setters and special decorators would be great!

It really like the joke in the beginning !!

Also, Thanks for talking about number 1 as to where it's place is. Never thought of 1 is be just a unit.

What is the code for the colors you use for coding? I would like to use it on my shell.

>because it's Prime time

hahaha you're awesome

>I am feeling some kind of an emotion, could it be joy?

LOL

Hahaha..!! Nice way of explaining! ..quite straight forward too. But i loved it. Thanks!!

I'm a beginner in Python and when I programmed to deal with prime numbers for the first time, I tried to eliminate the multiples of tested numbers every time from a list created to contain 2, 3 and numbers in the form of 6k+/-1 and it ended up a mess for some reason.

Brilliant!

What editor are you using?

There are other ways to optimize further, of course. All prime numbers, except for 2 and 3, are going to be equivalent to 1 or 5 mod 6. So you can test just two values per loop, and skip through with a step of 6. Might accelerate things a bit. In theory it should eliminate the number of divisibility checks to 2/3 of what your version 3 was doing.

You might also try divisibility by some small primes (2,3 and/or 5) right off the bat just to eliminate these composites. Testing for divisibility by just 2 and 3 cuts out 2/3rds of all numbers. Save yourself running through an O(sqrt(n)) loop 66% of the time.

Still we can reduce time by checking if that number is in the form of 6n+1 or 6n-1. Every prime no. Satisfy this condition

Also, all prime numbers excluding, 2 and 5, end in either 1, 3, 7, 9. So if the number ends in anything else it cant be prime. therefor you only have to test numbers that end in 1,3,7,9

I get a strong feeling I need to learn some more math to understand much of this better.

where can we find the code of programs written by you in ur video

Your videos are awesome..I am struggling with design patterns in python..can you post the tutorials for the same?

I did not understand this but it still made me learn something. Thx!

at 3:35 why not use >>max_divisor = int(n**0.5) ?

you lied at the first code, if you plug in 15 it will turn true

this program not working

# –

– coding: utf-8 ––"""

Created on Sun Feb 25 10:02:08 2018

@author: inban-pythonic

"""

lower = int(input("Enter the lower interval: "))

upper = int(input("Enter the upper interval: "))

for num in range(lower, upper+1): # range 5,6,7,8,9,10 but check 11 so +1

if num>1: # positive integer

for i in range(2, num):# 20 th century not prime number 1 so start 2.

if (num % i) == 0: # come zero prime number

break #loop control statements

else:

print(num)

even more efecient:

def getPrimes(t):

t0 = time.time()

primes = [2]

for n in range (3, t, 2):

md = 1 + math.floor(math.sqrt(n))

for d in primes:

if (n % d == 0):

break

if (d > md):

primes = primes + [n]

break

else:

primes = primes + [n]

t1 = time.time()

print("Primes lasted: ", t1-t0)

return primes

There is something that could've been done to improve the function, is_prime_v3(n). The first `if` should be `if n > 2 and n % 2 == 0:` as this serves as the strongest filter for non-primes. Secondly, use `elif` instead of `if` for the other two `if`s. Test it and you'll see it's faster!

Surprised to see posteriori analysis being used to analyse the algorithm. Better use apriori analysis for obvious reasons!

Wow thank you very much for this. I am taking number theory this summer, and this video helped me conceptually with some of the things I am learning, and also i get to learn a little bit of programming. Thank you!

sorry but when i entered a range between 1 to 40 it shows 25,27,35 are prime no

please fix this

Very nice lesson thanks a lot

for n = 2

n % d —— 2%2 = 0…. which gives false as output..

but 2 is a prime number… i feel there is some error in the program

first V result was (0.29421353340148926), second V result (0.29720377922058105), third one was a surprising (0.3161799907684326) so the first and second V the difference was fractions, while the third V it's a tenth difference!

Not working for 41..since (math.floor(math.sqrt(41)))= 6 hence it's divisible by 3, its the flaw of this program

Alternative

Take the input as n.

B=range(0,n)

If a>3:

If a%n==0:

Print("not prime")

Else:

Print("prime")

Else:

Print("prime")

According to that, 63 is prime.

I have the same program with range(100), but i see that for n=63, n=99 and others it shows me True, which is not right ? Also for n = 2 show me a None type because there is no case for n=2. I am using python 3.4.

Do you think i do something wrong ?

OMG you are so good! Could you make a video about improving the speed time of an algorithm that decompose a number into prime factors? Thanks!

for 10000 it still takes 67 seconds…

If you want it to run fast, use C.

Lol first do the right thing and write a doc string 😂

in 4:35 ".. if n > 2…" is redundant.

It is joy 🙂 – Thanks.

All primes (p), except 2 and 3, and multiples of primes, except multiples of 2 and 3, are 1= p mod 6 and 5 = p mod 6. So, starting at 7 one only needs to check for primality of every 4th, then 2nd number (n) by dividng by each in the range of 5 to the SQRT of n in alternating steps of 2 and 4.

Use

itertools'cycleto generate the alternating steps.2:12 Who else got 38.673019886016846 seconds?

Can somebody help me the purpose of adding a step value, third value in the for loop – Version 3 of the code.

I feel a kind of emotion too!

It is definite joy!

Came for python. Left with math lesson.

Can you plz tell me which software is this ?!!!

It took 0.528 seconds to calculate 10,000 times. But 74.35 seconds to calculate 100,000 time. Why? Shouldn't have it taken 5.28 seconds? Why did it took almost 100 times extra seconds instead of 10 times?

make the processor faster

if chipers of a number are all combined equal to a number divisible by three then it is not a prime, but that will also cost time.

all numbers that have 5 in end are not prime either (not including 0, since it is divisible by 2 and already incorporated).

Here is a better way to find primes: The Prime Locomotive.

The locomotive runs down the number line to the first number/tie. Finds no number there but does nothing because the number one is not a prime number. Continues on to the second number location which is the number 2. Finds nothing there, places the #2 into the prime file, places the #2 on the number line and multiplies it foreword (2,4,6,etc).

Locomotive continues to the third number location, finds nothing there, places number 3 in the prime folder, places the number three on the number line and multiplies it foreword (3,6,9,). Locomotive continues to the next number location, #4. Finds a number there ( the product of #2 being multiplied foreword) which means that number is not a prime, so it continues on past #4. Continues to the next number location, #5, finds no number there, places #5 in the prime folder, places #5 on the number line and multiplies it foreword (5,10,15,20,etc…). From then on the locomotive continues down the number line and wherever it come across an empty number location it files that number in the prime folder, places it in the number line, and multiplies it foreword. This will find every prime on the number line, however far down the number line you wish to travel.

Regard,

Russell Lee

why does this sound like the lady in hitman?

😂😂😂😂

i feel like i am watching Person of Interest …damn..this is gold

math.floor(math.sqrt(n)) + 1 is the same as math.ceil(math.sqrt(n))

Am I right?

Pretty creepy and serious but entertaining… Great video… Thank you

Thank you

you can delete statement below

if n > 2 and n == 2:

return False

and instead of that use:

"for n in range(3, 100000, 2):"

range(start, stop, step)

it produced a range of odd numbers ( like this 3, 5, 7, 9, 11, …..)

I see many people import math jsut for math.sqrt() which is a bit weird to me.

Is there a flaw with n**0.5 ?

I liked the intro , really futuristic

I really love the way of explaining concept n you made my concepts more clear. This video really helped me a lot.

Thank you n plz continue making such videos on programming problem solving approaches in efficient way

I made a code to print prime numbers in sequence:

————————————————————-

def tp(n):

for x in lx:

if(n%x==0):

return False

"""for i in range(n,1,-1):

if(1!=i!=n)and(n%i==0):

return False"""

return True

lx=[]

for i in range(2,10**7):

if(tp(i)==True):

lx+=[i]

print(end="%i, "%i)

————————————————————-

Python 3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:06:47) [MSC v.1914 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information.

>>>

===================== RESTART: H:PythonMathprimos.py =====================

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083 …

not a good explanation at all. It's hard for beginners to understand it.

only necessary to check divisors whose square is less than the test number.

I like the way the woman introduces the topic

Can she crash Mr.python by

🤪😱

python prime number pendulum?

like

bigbanG?

your explanation is awsome

do some videos on computer vision using python.

That's numberwang.

why do we need round down and add 1 in the range?.. i cant understand

When running the speed test of the is_prime() function that is based on the version in the video at 2:12 it took about .5 seconds for 10,000 and about 45 seconds for 100k trials. I would still say this is decent, but this algorithm can be significantly improved; continue watching Sacratica to find out how!

Next Up for Socratica: 2 New Series, Building a Full 3D Graphics Engine from Sratching using Vulkan and Creating a Full NES Emulator that can run Crysis!

Not working for 2

Excellent. I'd highly appreciate to see more of the kind of videos

i hope you are ready, cause its PRIMETIME

Sieve of Eratosthenes is still faster than v3 if properly implemented 😉

Support what you love! Socratica has a Kickstarter to make more Python: http://bit.ly/PythonKickstarter

why not use break statement and make it much faster? As soon as you find a number which it divides successfully apart from 1, then its not a prime.

will next step be to try only the prime numbers as divisors?

I want to get answer to this question

A program to take a number as input then display the sum of its factors

Does anyone have an idea why using filter in this case is slower than a for-loop? If you try the following function, which replaces the last for-loop with a filter, you will find out that it performs considerably worse. Also, why don't filter use multiple threads by default? It feels like it is build for it.

def isPrime(num):

if num == 1:

return False

if num % 2 == 0:

if num == 2:

return True

return False

end = int(math.sqrt(num))

factors = filter(lambda i: num % i == 0, range(3, end+1, 2))

return not bool(len(list(factors)))

omg, I like her presentation, not only cleared the vague of the subject but also presented it in a sie-fi way, lol

good job <3

thanks for such a great explanation!

We're halfway there. We still need your help! Support Socratica Python Kickstarter: http://bit.ly/PythonKickstarter

I am learning python for the last few months and your videos are one of the best among all the available videos on internet.

Thank you very much and wish you guys all the very best.

It's official! The Socratica Python Kickstarter was a success! Thank you to all of our supporters. Because of you, many more Python videos coming soon!! 💜🦉

Amazing! Amazing! This is fantastic!

Many thanks for share this experience.

Please, do make more videos with Python focusing in Mathematics problems.

how can you test just code and not have to make a whole executable file in pycharm? writing this code in the terminal does not let me go back and change/redo…

What is the bgm u used ?

No need to import math for sqrt just calculate n**0.5. Tks for the video! Excellent content.

its prime time!!!! half android, half human woman, can you guess the better half? neither can i. great video, subscribed, thanks so much!

Na lavadalo video

Welcome to Socratica! You can see our entire Python Playlist here: http://bit.ly/PythonSocratica

Subscribe to see all our new videos! http://bit.ly/SocraticaSubscribe

type ( emotion ) = joy

It's unprecedented.