Dijkstra's Hidden Prime Finding Algorithm

[@jhonnywhite1256]

Hey thx a lot for giving the code in your Patreon, really useful for my study

[@AlfW]

9:45 Actually, the Sieve of Eratosthenes isn't even using multiplication, it is only using addition.

[@rodrigoqteixeira]

9:16 small optimisation he didn't refer (I think I discovered it but anyway) you only have to uncheck the numbers of beeing primes starting on the now found prime squared. Ex: now you found that 11 is prime, you only need to uncheck the multiples starting at 11² = 121. Before that all the multiples are guaranted to already be unchecked by prior multiples for the same reason you only unmark the multiples of primes up to √n.

[@vuphamquang538]

Love your animation and the way you say "sh-mall"

[@CallOfCutie69]

This is the moment Walt became Heisenberg Prime.

[@alexbf4724]

Djikstra's algorithm is mindlblowing

[@greensalad_1205]

0:29 Trial of Erastosthenes

[@tododiaissobicho]

Djikstra was a legend, that's a really cool algorithm

[@nexcode_ir]

Woww, It was great. Thanks for sharing your precious knowledge

[@cppexplorery]

This man really does cool things 💪

[@yassine-sa]

Dijkstra's algorithm feels like it took the division approach and was like hold on we can memorize intermediate results of the division to avoid doing it all over everytime

[@Vaaaaadim]

To me it looks like the sieve of eratosthenes(I'll abbreviate as SoE) approach, but instead of maintaining a boolean array, we keep track of what is the next prime multiple we would mark, and update when we need to. Something that makes it a little less obvious is how for SoE, the video doesn't explain that we can start at the squares of the prime. When we mark the multiples of 7 for instance, we can start marking from 49 onwards, because 14,21,28,35,42 will already be marked by multiples of 2,3,5. If we think of SoE as running a loop for multiples of 2,3,5,7,etc then Dijkstra's alg keeps these loops in an intermediate state and does their next iteration when necessary.

[@dg636yt]

You guys both just proved that dijkstra successfully blended the two together @@Vaaaaadim

[@Vaaaaadim]

@@dg636yt Would you not say that SoE already does the "memorize intermediate results of the division" on its own?

[@dg636yt]

@@Vaaaaadim it's more of a tabulation approach than a memoization approach

[@KRYPTOS_K5]

3 times faster. It also shows Euler primes. Memory usage is minimal. You can play with in your Android. Really fast. If automatic compiled to native Java even faster. Good game. ! PRIMES ! Brasil. R.H.Hodara ! To US Mathcircle ! Prime? Euler Prime? ! RFO!Basic! Android Native Offline fn.def isEuler(x) y=x^2-x+41 IsEuler=y Fn.rtn IsEuler Fn.end fn.def IsPrime(n) IF n

[@911Salvage]

Dijkstra's algo is pretty easy to code. One of the very first assignments we got in data structures and algorithms course was to code Dijkstra's prime number algorithm in C or Java.

[@KRYPTOS_K5]

! PRIMES ! Brasil. R.H.Hodara ! To US Mathcircle ! Prime? Euler Prime? ! RFO!Basic! Android Native Offline fn.def isEuler(x) y=x^2-x+41 IsEuler=y Fn.rtn IsEuler Fn.end fn.def IsPrime(n) IF n

[@sandiguha]

Walter White before becoming a High school teacher

[@jimyaguasviva4461]

The best? Cache them all 🎉

[@Unprotected1232]

The key remaining challenge is how to make these algorithms scale on multi-core processors and GPUs.

[@zyklos229]

That's the sieve, but with minimum look-ahead, which saves space.

[@hallamw]

Thanks!

[@b001]

Thank you so much!!

[@14allfor1]

underrated

[@GabrielMancini1]

Wow great video

[@dtar380]

Math explanation for the sqrt thing, think of any number, well, its square root is just exactly the number that sits in the middle of all multiplications possible to get itself, because its the result of multiplying that number twice, if you increment by the number it wont match the original same if you decrease it

[@nomansbrand4417]

So this is what the late Walter White kept himself busy with at his hideout... !

[@indrajitpal63]

This is brilliant ! Thanks for sharing 😃

[@hamzacasdasdasd]

uses more memory but extremely fast a good trade

[@EmreAkdeniz42]

a brilliant video und a brilliant idea...

[@na50r24]

No idea if this is outdated but I'm prepping for a Datastructures and Algorithms exams and instead of using Modulo for the Sieve of Erast, you could instead do a nested loop use multiplication I'm more used to C, so I write it in C I don't think the Python one will be too different. I use 0 for False and 1 for True. C has a standard library for booleans but that's just a guy doing #define false 0 #define true 1 So yeah, I got used to writing it explicitly. for(int i = 2; i

[@KRYPTOS_K5]

This is 3 times faster. ! PRIMES ! Brasil. R.H.Hodara ! To US Mathcircle ! Prime? Euler Prime? ! RFO!Basic! Android Native Offline fn.def isEuler(x) y=x^2-x+41 IsEuler=y Fn.rtn IsEuler Fn.end fn.def IsPrime(n) IF n

[@mznidx]

this algorithm is 1624x faster than Dijkstra's algorithm from numpy import arange, ndarray # i use arange because it faster than range and i want to return array def is_prime(start: int, stop: int) -> ndarray: if not start & 1 == 1: # In the binary system, every prime number ends with a 1, so I use a binary comparison operation (( & )) to check if the last digit is not 1. return arange(start+1, stop, 2) # The condition is true if the starting number is even; therefore, I add 1 to make it prime and then step by 2 to yield a prime number each time. return arange(start, stop, 2) for Example: is_prime(2, 10) [3 5 7 9] and this for even def is_even(start: int, stop: int) -> ndarray: if not start & 1 == 0: return arange(start+1, stop, 2) return arange(start, stop, 2)

[@shadeblackwolf1508]

I'll raise this, if you hardcode 2, 3 and 5, you can gain speed using the fact that all primes are 6N + or - 1

[@DeathSugar]

There's more space efficient way to find primes similar to Dijkstra's algorithm called Pritchard sieve. It should use less memory than Dijkstra and has close to Eratosthenes's sieve performance.

[@AshishKadam]

Haven't seen such quality content in years, hats off to you sir! ❤😊

[@Ormusn2o]

Dijkstra does not need to hear all this, he is a highly trained professional.

[@supremeakahandsomelegit8187]

yo why does he look like Walter white but successful for his invention idea

[@rursus8354]

I think using Python as a test is misleading about the advantage. I get it that Dijkstra doesn't use division nor multiplication, which is a vast improvement on the age old computers that Dijkstra used. Iff my observation is true - it might be wrong - then his improvement will really show up when the algorithm is implemented in C *_as is customary_* when programming algorithms and integrating them into Python. Python is actually a very bad language for everything except fast prototyping. It is exceedingly slow and inefficient, but nevertheless it is used for numeric calculation since it is so easy and well-documented to integrate foreign C code.

[@christophergame7977]

As a child I learnt to pronounce 'sieve' as, using the International Phonetic Alphabet, 'sıv', not as 'siv', nor as si:v. Other uses of the vowel: as in 'kip', not as in 'keep'; as in 'slip', not as in 'sleep'.

[@swedishpsychopath8795]

Thank you Norway for inspireing Dijkstra to do this.

[@b43xoit]

How?

[@pedzsan]

With today’s CPUs, I would also look at which algorithm could be made to run multiple threads in parallel and / or use GPU type instruction set.

[@3am_eow]

You may also compare it to the sieve of Pritchard.

[@zsoltory4176]

A much shorter proof is the followin: If a natural number n is NOT prime, it must be divisible into two factors n=f1*f2. If both factors f1>sqareroot(n) & f2>sqareroot(n) we get the contratiction n=squareroot(n)*squareroot(n) < f1*f2 =n. So if n is not prime, its smallest divisor must be smaller than squareroot(n). If there is no such divisor, n must be prime. (sorry for my lousy Engish).

[@uselesscommon7761]

Okay woah this is the type of content that makes me sub immediately

[@forgotabhi]

I feel like I have found a goldmine! Loving your videos. Also what theme are you using?

[@kmjohnny]

An elegant presentation of some brilliant algorithm ideas.

[@lannapasher2914]

Walter Hartwell White

[@milanaanitha5506]

Please make a video on finding the max contiguous subarray sum

[@victorferreira5852]

Very interesting. I myself am a quantum computing physicist currently writing a paper for a quantum algorithm that we found to handle such prime identification tasks. Even though im very familiar with algorithms like that, i didnt know about this one from Dijkstra, so thats a really nice video!

[@Scudmaster11]

You do know there is a faster way to build that prime method... not jokeing... im modifying Dijkstra's algorithm

[@raxirex6443]

good informative video 👍

[@platypi_otbs]

Dijkstra has been my favorite mathematician since 1994. Just brilliant.

[@ctbram0627]

sectional + sieve == speed of sieve and fixed space

[@hulakdar]

the size requirement of sieve for 5 million should be around 625kb, not 8mb, if you use a bitmap, and not array of bools, so this is probably some python inefficiency

[@reeeeedmil]

i like the dijkstra's algorithm the most tbh

[@wing-it-right]

truly a good video

[@bennettzug]

14:20 I was curious and the time complexity of the sieve of eratosthenes is O(n log log n), which i think is the first algorithm i've seen like that lol

[@arghjain1949]

That 8.4 GB ☠️

[@sergejnekrasov7688]

For any human resource machine friends: Dijkstra's method becomes slower if your ALU has no mutliplication hardware :(

[@mandrak87]

Why not always skip even numbers larger than 2? No need to check them as they can never be prime (divisible by 2). Would save half the checks.

[@durgaprasad814]

Computer finds a number is even by finding modules of 2.

[@mandrak87]

@@durgaprasad814 True but you could use a boolean flag that flips back and forth to skip every other number.

[@matthewp1988]

You still have to check the other multiples to increment them. For example 12 at 12:26

[@durgaprasad814]

@@mandrak87 yes that operation will be faster. However can we parallelis the division approach

[@RyanLopez-z6q]

You can increment by 2 starting at 5

[@FloydMaxwell]

I believe it is pronounced "Siv". Cheers.

[@thevalarauka101]

"so instead we need to increment our smallest multiple" and suddenly my brain just goes like, oh yeah, that makes sense, that's why this algorithm is better

[@MrJasbur1]

Also, for the Sieve of Eratosthenes, there are tricks that use the fact that the perfect squares are just sums of consecutive odd numbers starting with 1. So, like 1=1^2, 1+3=4=2^2, 1+3+5=9=3^3… and the pattern has been proven to continue forever.

[@MrJasbur1]

Sorry, it’s that fact, plus the fact that you can start crossing out multiples starting with the square of the newly identified prime number in the sieve.

[@yash1152]

13:23 can you share the code for those functions? i want to see some implementation details 13:52 ok patrons

[@leftyxbuffalo]

There's no need to check any of the even numbers!

[@emreyaln7780]

actually, i knew that idea but i didn't know Dijkstra invented it

[@MI08SK]

It is possible to optimise the sieve of aritosta... implementation by storing booleans in one bit each. reducing memory by 8x

[@janhornbllhansen4903]

Nice presentation, but discussion seems a little off. I'd be interested to know when these algorithms break due to time/space requirements. Trial division will run and output primes until it runs out of memory, while sieve won't even start if you set limit sufficiently high.

[@dernett]

You can further limit the memory usage of Dijkstra's approach by only storing a new prime `i` in the pool if `i*i

[@user-pw5do6tu7i]

can't wait to be the smartass who asks the interviewer to specify which dijkstras algorithm I should implement

[@programmertheory]

I wonder. Were these algorithms optimized in any way? For example, the trial division method can be optimized for numbers greater than 3 by utilizing the fact all primes > 3 take the form of 6k +-1. Meaning assuming n > 3, we can put 2 and 3 in the primes list and then iterate over 5,7,11,13...n and not add the numbers in the list that are not prime, like 25, which is 6(4) + 1. This does improve the trial method by quite a bit.

[@lavneetjanagal]

Awesome video. Thank you.

[@zeus7914]

very nice. i hadnt heard of that method before. thanks for bringing it to light

[@marlonmarcello]

So glad KZbin recommended your channel, instant sub! Great content, clear and concise explanation and lovely visuals.

[@sentinelaenow4576]

I've found Miller-Rabin primality test to be extremely efficient, even for very large numbers, like 20 digit numbers.

[@Idan_Nesimov]

Amazing video, well done

[@andypyne]

I like the Miller Rabin Probabilistic Primality test. That's super quick, with the caveat that it's not calculating Primes, but is very accurate at finding candidates - but for any desktop method if finding Primes, Miller Rabin is faster and as accurate. Miller Rabin breaks down at numbers higher than a desktop computer can easily calculate anyway

[@b001]

Interesting, I’ve never heard of it. I’ll look into it. Thanks for sharing!

[@rakeshkumarrout2629]

This is quite amazing.can you make Video or share the video links of DSA with python??

[@TerjeMathisen]

If you are comparing algorithmic efficiency: space vs time, then I really think you should extend your sieve with a few very natural extensions: a) Making the array a bit array reduces the memory needed from 8 Mbit to 1 Mbit or 125 KB. b) Just skipping all the even numbers (just remember that 2 was in fact prime) reduces it by another 50% to 61.75 KB, at which point it fits easily in the CPU $L2 cache. c) If we also skip all multiples of 3, then there are only 2 candidate numbers to check in each group of 6, i.e. at this point we only need ~41 MB. d) One final step, removing all multiples of 5, means that we have exactly 8 remaining candidates in each group of 30 numbers, so memory usage is down to N*8/30 bits, which for N=1e6 means just 33 KB. Finally, when crossing out multiples of the current prime P, we only need to start at P*P, and then the following odd multiples, until we get to the (precalculated) sqrt(N) limit.

[@dtar380]

May we get the code for the Dijkstra's algo, mine is using 16 times more space than SoE, speed wise is alr, its in between SoE and TD, but im racking my brain with the memory

[@MaloHombre84]

In Dijkstras approach, why didn't you increment the multiples of 2 and 3 after adding 11 to the pool?

[@firstnamelastname-oy7es]

Booleans usually take up a byte in computers due to the way memory is accessed at the byte level, even though they are mostly used to represent true or false values. There's no reason not to use bits instead of booleans if memory efficiency is the main concern of the algorithm. 30 bits fits into 4 bytes, so you would only need to use 4 booleans worth of space instead of 30.

[@riteshkumar-ve3hs]

Where can i find the Python code for these 3 approaches?

[@Sandeepan]

How about a video on AKS test

[@mschoenert]

kzbin.info/www/bejne/emikeZWvdtGaf6M

[@FireszCh]

What theme you use in vs code? Plss reply

[@khennessy785]

Fantastic video, but you were driving me crazy talking about the sieve. Sieve is pronounced like "siv" not "seev"

[@codycodes7527]

this algorithm is witchcraft

[@rursus8354]

Why just test factors up to √n? Because if you test any number [√n ... n-1] the other factor is in the interval [2 ... √n] and that factor you already tested! Thus testing [√n ... n-1] is just duplicate work.

[@PatrickPoet]

fun video, thanks, I love stuff like this. your pronunciation of sieve isn't the British or American pronunciation, where is it from?

[@danmar007]

How many unique license keys can Microsoft generate using its 25-character key system? I would love to know because it would be real, whereas the number of grains of sand and celestial bodies is guesswork.

[@Grumpy6]

One of the most elegant and easy to understand videos dealing with prime numbers. Congratulations!👍

[@MrJasbur1]

Just a minor mention on trial division. We don’t have to explicitly calculate a square root. Instead, if we only go up to the largest prime number that can be squared to get a value still less than or equal to the value being trial divided, we know that’s the last prime number that has to be checked.

[@brian554xx]

For all of these methods, you can advance by two (rather than one) at each step starting at 3. From 3, you check 5, 7, 9, 11, etc., skipping over 4, 6, 8, 10, etc. without even checking them. It's a trivial change to the code and eliminates half of the numbers you would check. Also, for trial division, you don't need to compare each prime to the square root. Just find the square root and start there, working downward in the list of primes. This is fun. I miss this stuff!

[@Khwerz]

It's faster than sieve too, but this depends entirely on your CPU and languages array removal features. if its C its probably fast. but the only way sieve is faster is if you have a file FILLED with bools, 0/1, then you just seek to a position of the number and check if its 0 or 1.

[@chao.m]

Actually, beyond 6, you only need to test the numbers immediately surrounding a multiple of 6, eg, 11, 13, 17, 19, 23, 25, 29, 31… That way, you skip 2/3 of the natural numbers because you have skipped all multiples of 2 and 3. But it will be difficult to incorporate that into SoE or Djikstra’s algorithm

[@przemekkobel4874]

Wouldn't that break algorithm's requirement to update list of 'smallest multiples' on each tested number?

[@kvetter]

I implemented this feature of skipping even candidates--it was very good optimization. On my computer it reduced the time to find all primes under a million from 8.2 seconds to 3.8 seconds. It does break the "smallest multiple" requirement but the fix is to just update smallest multiple entry by 2*prime instead 1*prime.

[@levieux1137]

@@przemekkobel4874 yes it does. It still works to skip even values though, because for each equal value there are exactly two updates, so instead you perform your updates by adding twice the base value. But beyond that for now I failed to make it produce all good values (some are missing or some are extra depending on my tests).

[@dominiquecolin4716]

that would be interesting to find a 'green' measure that would take into account the CO2 cost of the data center + time of calculation for each approach. I think we should go for such stuff, because time always seems the most important, since data storage is not perceived as an issue any longer. It was different from 1970 til 2000.

[@juanmacias5922]

Dang, Dijkstra wouldn't take common consensus as the absolute, that's awesome, thanks for sharing, super interesting video!

[@spaghettiking653]

That's what makes the greats so great :)

[@simplefahrenheit4318]

Does the sieve of erasthosthanes (in modern) use units place being 1 , 3, 7 and 9 to create the initial boolean array because above 5 those are the only places of prime numbers

[@stanleydodds9]

There are several different ways to optimise the sieve of eratosthenes that massively reduce its space complexity, while keeping its time complexity the same. Note that the main benefit of this is actually to improve caching, and hence speed - memory in general isn't a problem, but not staying in the same place in memory for a while causes lookups to be much slower. The most obvious such approach is the segmented sieve. You divide your full range 1 through n into segments of size on the order of sqrt(n), and just sieve the blocks one at a time (with a small optimisation). The first segment is sieved as normal, to get an initial list of primes. Then for all subsequent segments, we already have all the primes needed to completely sieve them. So we only have to mark off composites using the primes we have already found, up to the square root of the largest value in the block. After that, we do one pass on the block, returning all the values that are prime (and adding them to the list of primes if needed).

[@davidwillmore]

That's what I did many years ago and it works very well. Id memory does become an issue, you can actually integrate this algorithm a third time, but at that point storage of the discovered primes becomes a significant task.

[@beasthunter4003]

Hi, can I please have your python font and background settings? I really like the way it looks, please share

[@SamDsk]

When it comes to large primes numbers we use probabilistic approach to determine whether the given number is a prime. They are called probabilistic primality tests like Miller-Rabin algorithm.

[@ezion67]

Your version of the "Sieve" seems to use a whole byte to store a bool instead of just one bit. That is a first huge space saving just up for grabs. The second is to forget about all even numbers other than 2. This can half the space the sieve needs and for trial division half the time. But in the long run Dijkstra still wins.

[@proosee]

There is a js lib for that

[@davidrubel6295]

Why would you test even numbers in the Trial Division method when you already know that even numbers greater than 2 are not prime. That's a waste of time

[@wooooooo_Oo]

Great video. Just a note on the color's chosen during the Sieve of Eratosthenes' Boolean Array. I'm red/green colorblind and had a hard time seeing true and false values because the false value was not distinct enough against the background. Another option is the yellows for true wasn't bright enough for me to quickly identify.

[@CrapE_DM]

This is the first time I've seen anyone apply the square root stopping point to the Sieve. Good to see it

[@mschoenert]

Nice video - talking about this algorithm that is not so well known. Note that your implementation of Dijkstra's algorithm is different from his implementation in an important way - that has consequences for both the performance and the memory footprint. You put the multiples into a heap - while Dijkstra puts them into an array. So all updates take logarithmic time in your implementation, while they take constant time in Dijkstra's. It is actually a little bit more complicated, because in Dijkstra's implementation it needs to scan the array until it finds a divisor. But that doesn't cost that much time, because for most of the candidates one of the earliest primes will divide them (half of the numbers are divisible by 2, one-third are divisible by 3, etc.) So overall your implementation is slower than Dijkstra's implementation. And you are also putting primes and multiples into that heap that don't need to be there. If you are trying to find all the primes up to N, then you only need to put primes P with P*P

[@prayagpatel9204]

Great insights thanks

[@Jack-oi8gn]

this was an amazing read, thank you!

[@rchas1023]

I have an elementary proof (from Erdos ) that there is a prime between N and 2N, for N >= 2, and I think that 2N

[@trueriver1950]

A trivial efficiency boost is got by ignoring all even numbers. To do this we need to do two things in startup: put 2 into the list to be output, but ignore it on all the trial divisions (or whatever method). Then start the prime search at 3, incrementing always by 2. This simple optimization saves testing half the numbers, and adds no complexity to the loop: all the added code is in startup. The next optimisation is to step in multiples of 6, for each N being a multiple of six we only have to test N-1 and N+1 because the other odd number must be a multiple of three. The easiest way to start this is actually to dummy in 2, 3 (neither of which is ever tested) starting with N=6, where both N-1 and N+1 are not tested as we never test for divisibility by 2 or 3. Another option would be to dummy in 2, 3, 5, 7 and start from N=12. In a long run this saves one more iteration, which is trivial compared to saving a constant fraction. My feeling is that this is less elegant than starting from 6, and not worth the tiny saving. This cuts another 1/3rd off the number of primary tests, at the cost of adding door to the loop, and that we have to dummy in the primes 2 and 3 which would otherwise be skipped. Likewise for each prime we know up front we can cut down a further fraction of the results to be tested, testing more primes in each iteration but fewer overall. I'll leave it to you to figure out which numbers to test starting from N=30 going up in 30s (there are more than two in each iteration). Stepsize 6 is ready to code and worth doing. Stepsize 30 harder, and stepsize ?? harder still: at this point another optimisation kicks in: and that's programmer time vs computer run time. If you are paying the programmer and paying for computer time it's then a cost based decision. If you own the computer and are doing it for fun then that optimisation depends where complexity stops being fun. When optimisation becomes tedious let the computer run whatever stage you've got working and tested at that point... OR you then write a program to create the program for the next stepsize What you don't do is ask ChatGPT to write the program 😉

[@trueriver1950]

Pedantic correction: there is a prime between every number >1 and it's square 😊

[@AK-vx4dy]

@13:55 I have some doubts, Dijkstra method should be much faster, slower than erastones (but i won't bet, it is not cache friendly) have simiilar operations, don't have suqare root and division, so speed should be in simmilar ballpark. I don't know python much so i guess problem lies in heappoll poping and pushing