If you're seeing this message, it means we're having trouble loading external resources on our website.

Хэрэв та вэб шүүлтүүртэй газар байгаа бол домэйн нэрийг *.kastatic.org and *.kasandbox.org блоклосон эсэхийг нягтална уу.

Үндсэн товъёог

# Primality test with sieve

## Video transcript

now to recap we are checking if some number n is prime by doing a trial division here is the square root of N and here is three starting at three and we were hopping along by two up until the square root of N and at each point in the way checking if that number divided n now so far people have been trying to reduce the number of steps we take by perhaps starting later and taking larger steps now I just want to pause here and let's think about what is the ideal case for a trial division algorithm what is the best we could possibly do if we got very creative and are stepping well remember any number n has some prime factorization right and let's say the square root of n is here we actually only need to step on prime numbers that would be the best we could do because we know if we step only on Prime's we will eventually find a factor prime factor if it's a composite the question now is how efficient is this method because it seems like we have a perfect solution now if we wrote a new algorithm which first just called the sieve let's say the new algorithm is calculating if n is prime it could call the sieve and generate a nice long list of primes for us and then we would have our trial division which would use this list of primes so it could hop along and hit only Prime's up until the square root of n wherever that is so what's wrong with this well we can visualize the time complexity or the number of steps taken and remember I did so by I coded up this algorithm and I put in a step counter inside each loop so we have um let's just say step plus plus means step plus one here and inside this other loop there's also a step counter step plus plus so these are all constant operation is checking if and and marking so we just have a step counter inside each loop and now here is a comparison on the far left is our old trial division method in the middle is our algorithm just calling the sieve to generate all primes up to n and on the right is this proposal where we just call the sieve to generate Prime's up to the square root of n and then call trial division just on those Prime's and let's see what happens with small input as we can see initially the the sieve takes many steps so even the modified version on the right is actually slower than trial division and as the input grows the number of steps in the sieve grows even faster so let's just forget the middle and compare trial division versus the sieve up to the square root of n plus trial division and here we can see the old trial division method is much more efficient the number of steps in our sieve to square root of n plus trial division is growing much faster so it is actually not an improvement and below is the program I use to do this comparison and there is a recording explaining how I set it up but now you may be wondering well what if we calculated the Prime's in advance so the first step would be to let's say build an array of primes and store it on a hard drive and then our algorithm would just do trial division and it would know how to hop on Prime's only because it would be reading from this proposed prime List and perhaps our prime List stores all Prime's up to 20 digits or even a hundred digits why can't we do this well the problem is limitations in memory when we enumerate lists of numbers which we'll explore next and just for example let's say we were doing this by hand we calculate 5 was prime we five on a piece of paper and we store it in a frying cabinet then we get seven we store that in the filing cabinet and nine or eleven sorry into the filing cabinet and then we have a filing cabinet full of prime numbers this is our think of it as a prime array now how big with this filing cabinet be if say we wanted all Prime's up to 20 digits or all Prime's up to 100 digits long could we even store this array on a hard drive and understand why this actually isn't possible we have to dive a little deeper into how large does this actually grow this prime array and what is the size limitation of modern-day and even future computer hardware