Dijkstra's Hidden Prime Finding Algorithm

Поділитися
Вставка
  • Опубліковано 12 січ 2025

КОМЕНТАРІ • 312

  • @jhonnywhite1256
    @jhonnywhite1256 6 місяців тому

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

  • @AlfW
    @AlfW 3 місяці тому

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

  • @rodrigoqteixeira
    @rodrigoqteixeira 25 днів тому

    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
    @vuphamquang538 Місяць тому

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

  • @CallOfCutie69
    @CallOfCutie69 9 місяців тому

    This is the moment Walt became Heisenberg Prime.

  • @alexbf4724
    @alexbf4724 11 місяців тому

    Djikstra's algorithm is mindlblowing

  • @greensalad_1205
    @greensalad_1205 8 місяців тому +1

    0:29 Trial of Erastosthenes

  • @tododiaissobicho
    @tododiaissobicho 7 місяців тому

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

  • @nexcode_ir
    @nexcode_ir 8 місяців тому

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

  • @cppexplorery
    @cppexplorery 10 місяців тому +1

    This man really does cool things 💪

  • @yassine-sa
    @yassine-sa 11 місяців тому +397

    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
      @Vaaaaadim 11 місяців тому +28

      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
      @dg636yt 11 місяців тому +16

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

    • @Vaaaaadim
      @Vaaaaadim 11 місяців тому +2

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

    • @dg636yt
      @dg636yt 11 місяців тому +4

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

    • @KRYPTOS_K5
      @KRYPTOS_K5 7 місяців тому

      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
    @911Salvage 7 місяців тому

    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
      @KRYPTOS_K5 7 місяців тому

      ! 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
    @sandiguha 4 місяці тому

    Walter White before becoming a High school teacher

  • @jimyaguasviva4461
    @jimyaguasviva4461 10 місяців тому +1

    The best? Cache them all 🎉

  • @Unprotected1232
    @Unprotected1232 10 місяців тому

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

  • @zyklos229
    @zyklos229 10 місяців тому

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

  • @hallamw
    @hallamw 11 місяців тому

    Thanks!

    • @b001
      @b001  11 місяців тому

      Thank you so much!!

  • @14allfor1
    @14allfor1 7 місяців тому

    underrated

  • @GabrielMancini1
    @GabrielMancini1 11 місяців тому

    Wow great video

  • @dtar380
    @dtar380 3 місяці тому

    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
    @nomansbrand4417 11 місяців тому

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

  • @indrajitpal63
    @indrajitpal63 10 місяців тому +1

    This is brilliant ! Thanks for sharing 😃

  • @hamzacasdasdasd
    @hamzacasdasdasd 4 місяці тому

    uses more memory but extremely fast a good trade

  • @EmreAkdeniz42
    @EmreAkdeniz42 11 місяців тому

    a brilliant video und a brilliant idea...

  • @na50r24
    @na50r24 7 місяців тому

    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
      @KRYPTOS_K5 7 місяців тому

      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
    @mznidx 8 місяців тому +1

    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
    @shadeblackwolf1508 10 місяців тому

    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
    @DeathSugar 10 місяців тому

    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
    @AshishKadam 10 місяців тому

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

  • @Ormusn2o
    @Ormusn2o 10 місяців тому

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

  • @supremeakahandsomelegit8187
    @supremeakahandsomelegit8187 Місяць тому

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

  • @rursus8354
    @rursus8354 10 місяців тому +1

    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
    @christophergame7977 11 місяців тому +1

    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
    @swedishpsychopath8795 11 місяців тому +1

    Thank you Norway for inspireing Dijkstra to do this.

    • @b43xoit
      @b43xoit 11 місяців тому

      How?

  • @pedzsan
    @pedzsan 10 місяців тому

    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
    @3am_eow 5 місяців тому

    You may also compare it to the sieve of Pritchard.

  • @zsoltory4176
    @zsoltory4176 10 місяців тому

    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
    @uselesscommon7761 10 місяців тому

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

  • @forgotabhi
    @forgotabhi 10 місяців тому

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

  • @kmjohnny
    @kmjohnny 10 місяців тому

    An elegant presentation of some brilliant algorithm ideas.

  • @lannapasher2914
    @lannapasher2914 5 місяців тому

    Walter Hartwell White

  • @milanaanitha5506
    @milanaanitha5506 10 місяців тому

    Please make a video on finding the max contiguous subarray sum

  • @victorferreira5852
    @victorferreira5852 10 місяців тому

    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
    @Scudmaster11 10 місяців тому

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

  • @raxirex6443
    @raxirex6443 11 місяців тому

    good informative video 👍

  • @platypi_otbs
    @platypi_otbs 11 місяців тому

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

  • @ctbram0627
    @ctbram0627 4 місяці тому

    sectional + sieve == speed of sieve and fixed space

  • @hulakdar
    @hulakdar 11 місяців тому

    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
    @reeeeedmil 11 місяців тому +190

    i like the dijkstra's algorithm the most tbh

  • @wing-it-right
    @wing-it-right 11 місяців тому

    truly a good video

  • @bennettzug
    @bennettzug 10 місяців тому

    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
    @arghjain1949 11 місяців тому

    That 8.4 GB ☠️

  • @sergejnekrasov7688
    @sergejnekrasov7688 11 місяців тому +1

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

  • @mandrak87
    @mandrak87 11 місяців тому +6

    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
      @durgaprasad814 10 місяців тому

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

    • @mandrak87
      @mandrak87 10 місяців тому +2

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

    • @matthewp1988
      @matthewp1988 10 місяців тому

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

    • @durgaprasad814
      @durgaprasad814 10 місяців тому +1

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

    • @RyanLopez-z6q
      @RyanLopez-z6q 3 місяці тому +1

      You can increment by 2 starting at 5

  • @FloydMaxwell
    @FloydMaxwell 11 місяців тому +1

    I believe it is pronounced "Siv". Cheers.

  • @thevalarauka101
    @thevalarauka101 11 місяців тому +1

    "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
    @MrJasbur1 10 місяців тому

    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
      @MrJasbur1 10 місяців тому

      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
    @yash1152 8 місяців тому

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

  • @leftyxbuffalo
    @leftyxbuffalo 10 місяців тому

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

  • @emreyaln7780
    @emreyaln7780 11 місяців тому

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

  • @MI08SK
    @MI08SK 10 місяців тому

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

  • @janhornbllhansen4903
    @janhornbllhansen4903 10 місяців тому

    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
    @dernett 6 місяців тому

    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
    @user-pw5do6tu7i 11 місяців тому +47

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

  • @programmertheory
    @programmertheory 10 місяців тому

    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
    @lavneetjanagal 11 місяців тому

    Awesome video. Thank you.

  • @zeus7914
    @zeus7914 11 місяців тому +4

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

  • @marlonmarcello
    @marlonmarcello 11 місяців тому +2

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

  • @sentinelaenow4576
    @sentinelaenow4576 10 місяців тому

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

  • @Idan_Nesimov
    @Idan_Nesimov 11 місяців тому

    Amazing video, well done

  • @andypyne
    @andypyne 11 місяців тому

    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
      @b001  11 місяців тому +1

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

  • @rakeshkumarrout2629
    @rakeshkumarrout2629 9 місяців тому

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

  • @TerjeMathisen
    @TerjeMathisen 10 місяців тому

    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
    @dtar380 3 місяці тому

    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
    @MaloHombre84 10 місяців тому

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

  • @firstnamelastname-oy7es
    @firstnamelastname-oy7es 10 місяців тому +2

    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
    @riteshkumar-ve3hs 8 місяців тому

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

  • @Sandeepan
    @Sandeepan 11 місяців тому

    How about a video on AKS test

    • @mschoenert
      @mschoenert 10 місяців тому

      ua-cam.com/video/D7AHbyAlgIA/v-deo.html

  • @FireszCh
    @FireszCh 7 місяців тому

    What theme you use in vs code? Plss reply

  • @khennessy785
    @khennessy785 10 місяців тому

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

  • @codycodes7527
    @codycodes7527 10 місяців тому

    this algorithm is witchcraft

  • @rursus8354
    @rursus8354 10 місяців тому

    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
    @PatrickPoet 10 місяців тому

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

  • @danmar007
    @danmar007 10 місяців тому

    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
    @Grumpy6 11 місяців тому +2

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

  • @MrJasbur1
    @MrJasbur1 10 місяців тому

    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
    @brian554xx 11 місяців тому +13

    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
      @Khwerz 11 місяців тому

      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
      @chao.m 10 місяців тому +1

      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
      @przemekkobel4874 10 місяців тому

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

    • @kvetter
      @kvetter 10 місяців тому +1

      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
      @levieux1137 9 місяців тому

      @@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
    @dominiquecolin4716 10 місяців тому

    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
    @juanmacias5922 11 місяців тому +164

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

    • @spaghettiking653
      @spaghettiking653 10 місяців тому +1

      That's what makes the greats so great :)

  • @simplefahrenheit4318
    @simplefahrenheit4318 10 місяців тому +1

    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
    @stanleydodds9 11 місяців тому +28

    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
      @davidwillmore 10 місяців тому +2

      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
    @beasthunter4003 8 місяців тому

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

  • @SamDsk
    @SamDsk 10 місяців тому

    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
    @ezion67 11 місяців тому +6

    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
    @proosee 11 місяців тому

    There is a js lib for that

  • @davidrubel6295
    @davidrubel6295 10 місяців тому

    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
    @wooooooo_Oo 10 місяців тому

    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
    @CrapE_DM 11 місяців тому

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

  • @mschoenert
    @mschoenert 11 місяців тому +195

    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
      @prayagpatel9204 11 місяців тому +12

      Great insights thanks

    • @Jack-oi8gn
      @Jack-oi8gn 11 місяців тому +4

      this was an amazing read, thank you!

    • @rchas1023
      @rchas1023 11 місяців тому +2

      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
      @trueriver1950 11 місяців тому +8

      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
      @trueriver1950 11 місяців тому +2

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

  • @AK-vx4dy
    @AK-vx4dy 11 місяців тому

    @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