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

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

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

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

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

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

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

  9. 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!

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

  11. 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!

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

  13. 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!

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

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

  16. 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 ?

  17. 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!

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

  19. 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?

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

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

  22. 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, …..)

  23. 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 ?

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

  25. 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 …

  26. 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!

  27. 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!

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

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

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

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

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

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

  34. Amazing! Amazing! This is fantastic!
    Many thanks for share this experience.
    Please, do make more videos with Python focusing in Mathematics problems.

  35. 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…

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *