# Python and Prime Numbers || Python Tutorial || Learn Python Programming

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.

## 100 thoughts on “Python and Prime Numbers || Python Tutorial || Learn Python Programming”

1. Kamlesh Kumar says:

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.

2. kennyPAGC says:

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

3. kennyPAGC says:

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

4. TheWelshGamerVII says:

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

5. kendout says:

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

6. Ulf Gjerdingen says:

aaaw <3

7. Vikas Sharma says:

Never seen this superb way to teach awesome stuff

8. MIGHTYx * says:

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))

9. PoeticJustice1288 says:

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

10. Ubaid Malik says:

It really like the joke in the beginning !!

11. Ubaid Malik says:

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

12. Isaac Rivas says:

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

13. Greed says:

>because it's Prime time
hahaha you're awesome

14. Greed says:

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

LOL

15. Shashi Kamal Chakraborty says:

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

16. 一宇八綋 says:

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.

17. Tsog Gantumur says:

Brilliant!

18. sourav choudhary says:

What editor are you using?

19. CogitoErgoCogitoSum says:

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.

20. navikesh doddi says:

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

21. TheZixxle says:

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

22. WHITE POWDER says:

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

23. Mahi MSD says:

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

24. priyesh8590 says:

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

25. Shiba Inu says:

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

26. Ahmed Amr says:

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

27. samuel natanael says:

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

28. Akash Kaintura says:

this program not working

29. Inban Pythonic says:

# –– 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)

30. Pedro Jorge Nunes says:

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

31. Farzin F says:

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!

32. Lakshay Kakkar says:

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

33. Joey M says:

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!

34. Hota Amit says:

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

35. med haouch says:

Very nice lesson thanks a lot

36. Pushpak pugal says:

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

37. Bassem Kabesh says:

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!

38. Srajat Mathur says:

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

39. Ayush Purohit says:

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")

40. Matheus Rocha says:

According to that, 63 is prime.

41. Mihai Dinca says:

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 ?

42. Code says:

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!

43. Rohit Bhati says:

for 10000 it still takes 67 seconds…

44. Lincoln Sand says:

If you want it to run fast, use C.

45. Nicholas Coffey says:

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

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

47. Tamer Aziz says:

It is joy 🙂 – Thanks.

48. K. Chris Caldwell says:

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' cycle to generate the alternating steps.

49. Nikhil Kartha says:

2:12 Who else got 38.673019886016846 seconds?

50. Rajesh Gokul says:

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

51. Tao Hu says:

I feel a kind of emotion too!
It is definite joy!

52. Kin Cheng says:

Came for python. Left with math lesson.

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

54. S M Fahim says:

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).

56. zola mo says:

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

57. Abhiraj Kale says:

why does this sound like the lady in hitman?

58. Ghost Hunter says:

😂😂😂😂

59. Winict Maximus Cosmo says:

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

60. Alexey Lagunov says:

math.floor(math.sqrt(n)) + 1 is the same as math.ceil(math.sqrt(n))
Am I right?

61. Arif Zuhairi says:

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

62. Mohamed .Bakr says:

Thank you

you can delete statement below
if n > 2 and n == 2:
return False
"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, …..)

64. MachiToons - Machimations says:

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 ?

65. Luis Valdez says:

I liked the intro , really futuristic

66. Urmila Gundeli says:

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

67. Daniel 91953574 says:

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

>>>

===================== 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 …

68. Warriorx1 Nino says:

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

69. Daniel von Bose says:

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

70. Asante Theophilus says:

I like the way the woman introduces the topic

71. Ikk0 M says:

Can she crash Mr.python by
🤪😱
python prime number pendulum?
like
bigbanG?

72. Rajat Mehta says:

73. Kaarthigeyan Rajendran says:

do some videos on computer vision using python.

74. Graham MacLeod says:

That's numberwang.

75. Chris LAM says:

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

76. skilz8098 says:

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!

77. skilz8098 says:

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

79. Robert Alaverdyan says:

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

80. calvin atuhaire says:

i hope you are ready, cause its PRIMETIME

81. Frank Willeke says:

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

82. Socratica says:

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

83. Rohit Dhage says:

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.

84. Mustafa Kalafat says:

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

85. Bhagya Laxmi Sahoo says:

I want to get answer to this question
A program to take a number as input then display the sum of its factors

86. Aleš Pecka says:

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)))

87. Nico Robin says:

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!

89. Socratica says:

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

90. utpal dutta says:

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.

91. Socratica says:

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!! 💜🦉

92. Rafael Lima de Souza says:

Amazing! Amazing! This is fantastic!
Please, do make more videos with Python focusing in Mathematics problems.

93. ida rahmqvist says:

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…

94. Manideep says:

What is the bgm u used ?

95. Gerardo Moscatelli says:

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

96. Morgan Sippel says:

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

97. movie info says:

98. Socratica says:

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

99. MiXxer says:

type ( emotion ) = joy

100. Superlative CG says:

It's unprecedented.