For this setup, where we are explicitly checking primes one at a time sequentially, if we dedicate some memory to storing previous primes, and only check our list of primes from 2 to sqrt(value), this saves a massive amount of time.

@YashBeanz

2 жыл бұрын

Yeah I was thinking about only dividing by previous prime numbers because all numbers can be factored into only prime numbers. Checking if a number is divisible by non-prime numbers would be pretty slow.

@ferociousfeind8538

2 жыл бұрын

I don't know the exact proportion of primes to total integers, though I recall it scales roughly with log(n)? Which would be equivalent to reducing an O(n^2) algorithm right down to an O(n log n) algorithm

@johnbachner9901

2 жыл бұрын

1/log(n) prime number theorum

@ferociousfeind8538

2 жыл бұрын

@@johnbachner9901 yeah, that sounds right, for any integer N there is a roughly 1 / log(N) chance it'll be prime, which means cataloging primes when we find them will be much more efficient than checking every integer up to sqrt(N)

@jaserogers997

Жыл бұрын

Sieve of Eratosthenes

18:50 you picking out 2137 randomly out of all prime numbers hit me like a bag of bricks

@SleepyHarryZzz

Жыл бұрын

Go on?

@golvanontheroad

Жыл бұрын

@@SleepyHarryZzz Polish meme. Pope jp2 died at 21:37

@itscartoonguy

Жыл бұрын

i see that im not the only one

I love the direction you're taking your channel, Daniel, very nice editing and explanation! You were the reason I started coding a couple of years ago and I honestly can't thank you enough! I am currently studying computer science at university, thank you for your wonderful channel!

@TheCodingTrain

2 жыл бұрын

Thank you for this kind feedback!!

@dinoswarleafs

2 жыл бұрын

Same! I saw his purple rain video in high school and it got me into Processing. I'll graduate next year with a BS in CS partially thanks to him haha

@GamilovesYou

2 жыл бұрын

@@dinoswarleafs Me too except I'm two years behind

@chandanrajkhowa1563

2 жыл бұрын

Tbufv

@michaelwalker1013

2 жыл бұрын

I also got motivated to learn to code because of him now I’ve been doing it for 4 years now I started after seeing his snake coding challenge!! Thanks Dan you are the best

O nie! Coding Train wybrał papieżową liczbę o 18:53, to znak :D

@reniferbobob8938

2 жыл бұрын

Boży kontent!

@jgtb0pl

2 жыл бұрын

Piękne

@erykzubowicz7837

2 жыл бұрын

: OOOO

@qerku_5640

2 жыл бұрын

I do tego sama spirala została wymyślona przez Polaka o:

@kretgwiazdonos7397

Жыл бұрын

na następnym odcinku unboxing pierogow

Love the fact that you showed your thought process, mistakes and frustrations, since that is exactly what everyone goes through when trying to solve a problem and portrays a realisitic view of what programming is. There are so many programming „tutorials“ out there that show you the perfect answer to a problem and act as if everything leading up to the solution made sense and was obvious, showing no mistakes at all. Which might make you think that they guys are so much better than they actually are and that you are just bad at programming. Really informative and entertaining video.

While I appreciate all the machine learning videos, I really like simpler ones too: some cool math and fun visualizations. Loved this one!

@TheCodingTrain

2 жыл бұрын

Thank you! I'm trying to focus on this style of video for a bit though I do want to get back to the sequenced tutorials.

@SijanModz

3 ай бұрын

Simple yeah right. Im just fcking retarded. Hate my life.

16:30 it is enough to check whether the number is divisible by another number less than the square root of the former because if you find the latter one you can also find another factor which is greater than the square root of the first number.

@englishish

2 жыл бұрын

I came to the comments to post exactly this!

@PMA_ReginaldBoscoG

2 жыл бұрын

@@englishish happy to see that someone thought the same way I did 😘

@comedyclub333

2 жыл бұрын

While this way mentioned in the video, there are also more optimizations that can be applied, e.g. testing the 2 separately and than testing it only for odd numbers (making the for loop start at 3 and increasing it by 2).

@englishish

2 жыл бұрын

@@comedyclub333 That idea is often included in whatever algorithm is being used to determine whether or not the number is prime (e.g. Sieve of Eratosthenes). That being said, it doesn't really do much in terms of reducing computing time : n/2 is asymptotically equivalent to n, whereas ✓n is significantly 'smaller' - e.g. for a number on the order of, let's say, 10⁶, eliminating evens still means you still have make on the order of 10⁶ 'checks'. By reducing things down to ✓n, you're down to ~10³ 'checks'.

@comedyclub333

2 жыл бұрын

​@@englishish I understand what you are trying to say but I disagree with your argument. Of course it significantly reduces computing time. I think you are mixing up computing time and asymptotical behavior. While n/2 scales the same way as n (= it's of the same order) it is still about twice as fast (= number of executed operations). So it really "does much". This is often mixed but technically not the same as the order expressed with the Big O notation does not really say anything explicit about computation time but more about scaling behavior and efficiency. Also my suggestion was not meant to replace the sqrt(n) suggestion.

I just wanted to stop by and say that when I was in high school several years ago I watched these videos and it really piqued my interest in computer science in such an engaging way. That was one of my first introductions to this field and inspired me so much that now I'm about to graduate with a degree in computer science this spring. Now I'm going through these coding challenge videos again with a much deeper understanding and it's enjoyable to know what's going on this time. Thank you so much!

@TheCodingTrain

2 жыл бұрын

Wow, I love hearing this story!!

@ledues3336

2 жыл бұрын

Wow I was about to comment my story which is very similar! His videos started my interest too, he’s a great guy

@TheCodingTrain

2 жыл бұрын

@@ledues3336 Keep these stories coming! 🚂❤️

@dubito_joy

2 жыл бұрын

me either, after I've learned nature of code from college, I changed my field from digital art to programming

I love these simple coding challenges!! So informative.

@TheCodingTrain

2 жыл бұрын

Super glad to hear!

@pvic6959

2 жыл бұрын

@@TheCodingTrain Coding challenges is how I found the channel and its still my favorite part! Thank you for still doing these!!

I love how you make so many pretty examples just so you can show them for a couple of seconds at the end. You put a lot of effort!

@TheCodingTrain

2 жыл бұрын

Thank you! The code for these is also included!

When I designed this, I created a grid that stored every number, and rotated around the spiral by always trying to turn left, and only kept going forwards instead if the spot to the left wasnt empty.

@TheCodingTrain

2 жыл бұрын

Well, that's a lovely way of implementing this!

Whenever I'm feeling the effects of the impostor syndrome I watch a coding video on KZread and my confidence returns.

I realize I'm a few months late on this but the number of steps you take on each side matches with the location of the perfect squares (1, 4, 9, 16, 25, and so on). If you had started your spiral with 0 in the center, then the perfect squares would be directly on the upper left and bottom right corners of the spiral. Since you started at 1, they're shifted 1 step back from the corners. Of course, in your project what you're doing is quite good but if you wanted to start somewhere ahead (say ignore the first 1000 numbers) you can figure out your position and step size by consulting the perfect squares (and their roots)

Every once in awhile this channel surfaces in my feed (yes, I'm subscribed). I always feel so uplifted after watching his videos. Daniel's enthusiasm is contagious.

Just a quick optimization for your isPrime routine. Simply compare the squared numbers so you don't need the expensive sqrt call, i.e. i * i Well, unless i^2 becomes to big for its underlying data type, of course.

@TheCodingTrain

2 жыл бұрын

Yes, great tip!

@killereks

2 жыл бұрын

just use sieve of eratosthenes

@RajJaiswal538

2 жыл бұрын

Or better than that,keep sqrt(value) in a variable and check i for that variable, By this,you're not squaring i for each iteration and calculating sqrt only once also,at start,if (value%2==0 && value!=2){return false;)

@i_am_aladeen

2 жыл бұрын

@@TheCodingTrain You can also optimize a bit more by only checking with odd numbers. After you have checked if the number is divisible by 2, then all other even numbers are already checked. In the same way, you can leave out all the numbers in between primes: You only need to check if the number is divisible by prime numbers up to the squareroot of the number.

I am a senior software developer. Sometimes I don't focus on what you are coding while other times I don't understand what and how you are doing something? I come here to find fun in your videos which the way you teach. At the end of the day I always return taking a happy and smiling face. Never fail.

@aycayldran8248

Жыл бұрын

I just wondering, why a senior software developer ever needs ulam spiral.This is my uni project for the first year and I thought i will never need this in my life ever again

Awesome stuff as usual. Hadn't seen the Theme Selector in Processing *or* that you can execute functions from the console. So cool!!

@TheCodingTrain

2 жыл бұрын

Super glad to hear!

@NuGeera

2 жыл бұрын

That was cool af

@Rolembeek33

2 жыл бұрын

Looks like my editor still can't execute from the console (no prompt and no reaction when typing there) Is there an update to do or something else ? (looked for it but couln't find) (Usin Chrome in Win10)

@TheCodingTrain

2 жыл бұрын

@@Rolembeek33 Maybe come and ask for help in the coding train discord? thecodingtrain.com/discord

I actually did that exact spiral algorithm on my own one day. I was making a game where a unit had to brute-force explore every tile on a map. That was the algorithm I came up with.

Prime numbers are amazing, there is always something to learn from them

You motivates me so much! Love your work!!

@Drxxx

2 жыл бұрын

Great

Your energy and optimism are infectious!

The amount of knowledge that is going into these videos is just phenomenal. When he calls out his own mistakes and makes it more fun to solve it is just amazing to watch

I've just started learning JavaScript and p5, and I decided to watch through your old videos. They. are. AMAZING! Not only is your style super engaging and fun but you're also very time conscious with snappy editing and concise explanations! Keep it up man! ♥️

@TheCodingTrain

2 жыл бұрын

Appreciate the kind feedback!

You’re like a second web development teacher for me. I attend university and I’m in a p5js-based web dev class. you’re the professor i never knew i needed.

Theme selector for processing is just... AMAZING

btw i'm a young teenager and learned javascript when i saw your snake video. Now I know c++, c#, java, javascript and python. all thanks to you!😍

@TheCodingTrain

2 жыл бұрын

Wow, I love hearing this story!!

I miss out on so many years of videos, come back and Daniel still have moments of struggle, gives me hope I can get work! Thank you for showing the process for so many years. :)

@TheCodingTrain

2 жыл бұрын

Welcome back!

this is timed so perfectly for me, i've been contemplating this sort of stuff the last 6 months and at the same time have been watching some of your older videos. I'm hoping to build something that's based on this spiral

I love you, Mr. Coding Train! You are far out, man.

This is the first video I've watched from your channel, as the algorithm blessed me with it at random and the topic seemed neat. You did a great job making it interesting and informative, I'll definitely be watching more.

i love the new direction this channel is going, the editing work is fabulous

i didnt undertand 99% of this but i sat through every second of the video lol youre a natural born teacher my friend

this is super interesting! I've been coding 4 months and was just trying to understand prime numbers. This really helped me out!! Thank you!

ありがとう御座います。 とてもいい勉強になりました！ これを参考にして、 私の求めていた答えが一歩でも、 近づけるような気がします! 応用してみます！

I love that the coding challanges are back!

Awesome ! each time I watch one of your video I learn something amasing ! Thanks for your passion ! Your channel has become one of my favorite. Great work. I can't wait for your updated version of the nature of code book ! let us know the timing when available.

Been watching u since forever, love ur vids so much

16:26 Speaking of efficiency, you could save the primes found in an array and just check the modulo with those already found primes. You don‘t need to check if a number is divisible by 12, if you know that it isn‘t divisible by 2 or 3.

@TheCodingTrain

2 жыл бұрын

Ooooh. Great suggestion!!

@Lotschi

2 жыл бұрын

@@TheCodingTrain Thanks. I appreciate your appreciation. 😁

@johannes8144

2 жыл бұрын

That's improving an inefficient design, the fastest way to compute primes is with the Sieve of Eratosthenes until like 10^13 then a linear sieve algorithm takes over. Just a quick side note :)

@Lotschi

2 жыл бұрын

@@johannes8144 What is the sieve of Erastosthenes?

@spaghettiking653

2 жыл бұрын

@@Lotschi It's an algorithm for finding all the primes up to a certain value, e.g. 100. The important part is that the value is preset, so you calculate a bunch of primes in bulk. Essentially, you start from 2, which you declare prime, and then mark every single multiple of 2 in the list of numbers you're testing as composite. Therefore, none of those will be considered prime, and you proceed to the next number. If the next number was not marked composite by the previous step, then it must be prime, so you repeat the same step again for all numbers. Through this process, the next number is 3, and therefore marks 6, 9, 12, 15, 18, etc. as composite since they are multiples. Going through for all numbers in the range gives you all the numbers' primality as a list of booleans, so it is easy to see whether a number is prime by checking the respective index in that list. Sorry for this soup of letters, but if you want a better explanation, I'd recommend you check out the Wikipedia article: en.wikipedia.org/wiki/Sieve_of_Eratosthenes

man, your enthusiasm is great

Hi Daniel You are a legend. You are so energetic and funny with your teaching. I randomly pick any coding challenges of yours and must say I enjoy each of them as much as all the others Thankyou for such great content.

This not only made me laugh out loud while at the gym, but I also learned a lot. Your presentation skills are phenomenal.

I love the post-processing animations!

You can also try drawing the circles on multiples of a certain number (multiples of 7, of 13 etc.). You can generate really cool patterns that way too.

@TheCodingTrain

2 жыл бұрын

Ah, thank you, I will try this!

I loved your video, it’s great content you’re showing. Keep it up ❤

You are so relatable with all the happy little accidents during coding. ☺️

man, you look so different yet similar to when you made the coding challenge #1 Love the content man, keep going!

@TheCodingTrain

2 жыл бұрын

It's been almost 6 years!!!

@Pywon

2 жыл бұрын

@@TheCodingTrain Time flies doesn't it? 😅

I didn't knew that we can make such things with code, huge thank you !

Hello sir, you have truly inspired me to code and are the reason I have learned machine learning.

I just love watching these videos. Thank you for these incredible videos

@TheCodingTrain

2 жыл бұрын

Appreciate it!!

I just recently found this channel and I just wanna say I love this channel :D

oh.my.god i love the coding challenges😍

Dear Daniel I just wanted to let you know how thankful I am for your hard work and your passion for teaching! Four years ago I had to pass a programming exam in uni, I struggled a lot as I hated coding and I was super bad at it. But you made it fun easy to understand. I simply couldn't have done it without your channel. Now I am even coding/scripting in my free time :) Thank you 1000x!!

@TheCodingTrain

2 жыл бұрын

Wow, I love hearing this story, thank you!

I swear your channel is my new favorite. I am gonna come by sometime on the stream and say hi.

I LOVE THIS CHANNEL WOOOOWW Keep going!

I grew up watching you....Thanks for all the knowledge you shared❤️

Your videos always inspire me to try new things!

I remember watching your videos back in 2017 or 2016 (?), i remember the maze generation challenge. It really prompted me to do some in-house learning of programming. And now by the magic of alorithm youtube's shown me your video again and it's so fun to see you're still going with the challenges - I have over 3 years of experience as web dev now and it's just fun to see "before" and "after" how I see the code you're writing. From black magic to pretty understandable logic :D

Great lesson, love the added visuals!

The animations are one point lately. Thanks for the content, such a fun channel.

I think you should do the N-Body Problem next as it is on exactly the opposite side of the arrow! Great video btw! 😍

@TheCodingTrain

2 жыл бұрын

Hah how did you know???

@Fun-Planet

2 жыл бұрын

Congrats, you guessed the next coding challenge!

@neillunavat

2 жыл бұрын

@@TheCodingTrain oh my god?! That's crazy!!

As always, great content!

it always so fascinating to seeing how you reasoning

I am loving the animations.

For the final test it would make sense to choose random odd numbers, not all numbers - since we did observe in the small example that excluding even numbers fell nicely on a diagonal, so just having that exclusion in the nature of primes might be helping the non-randomness appear in the image.

Thanks for these videos, really great.

Dude, love the concept. Teaching but hidden under a friend-youtuber type of video. Amazing

Thats fantastic

did that challenge last year using p5 js. Still fun to watch!

@TheCodingTrain

2 жыл бұрын

Please share yours!

@Vanawy

2 жыл бұрын

@@TheCodingTrain Created PR just now

Amazing, thanks for creating these!

@TheCodingTrain

2 жыл бұрын

Thanks for watching!

23:10 waiting inpatiently for this! Great video absolutely love your energy

Man that was really cool. Thanks!

Such a great explanation and that debugging session were so fun :D. Thanks for creating these types of videos...you are great!

@TheCodingTrain

2 жыл бұрын

Appreciate the kind feedback!

The miller-rabin primality test is a pretty nice one, and makes a lot of sense for anyone who knows modular arithmetic!

@benjaminwinters678

2 жыл бұрын

Finally a comment with a reasonable primality test heh. Doing something linear like he does works fine for small numbers, but its useless for large numbers. I just finished implementing RSA and needed to find 512 bit prime numbers.

I loved this video. Way back I have coded such an algorithm to draw a spiral on a checkered board (as part of a board game adaption) and was curious if Dan and myself have found the same simple algorithm or if there would be another (even simpler?) solution. We both came to the almost same solution. I just did not use a switch case statement, but controlled the change of direction in an array of direction coordinates which I then accessed using turnCounter % 4.

That was a cool introduction to Javascript and Java! Very cool :)

dude, this is amazing. thanks 😄

The zoomed out image you have on screen from 22:34 to 22:35 is fascinating. It shows a grid pattern in and of itself. There are almost concentrical squares that go out of dead space where there are no to little prime numbers. I'd love to see pictures of this zoomed out even further in various steps.

@wizziamthegreat

Жыл бұрын

pretty sure thats just artificing from grids that have a transformation applied viewed on a computer screen

22:30 the patterns are reminiscent of a tiled texture, like when you're looking out over an ocean in an old video game. There are obvious repetitions in the peaks and valleys and it's surprisingly square. Did not expect that.

fire content homie!

Woow, amazing channel, so much to learn.. thank you !

Amazing content, thank you!

love ur content

An easy optimisation to calculate prime numbers is by also only testing for prime numbers lower than the square root of the number your checking. You don't need to check if it's a factor of 4 if you know its not a factor of 2 already. And as your calculating primes as you go, just make a list of these and use them for the code

KZread just show this video in random.. And honestly this is the first video am watching on youtube that is super friendly, building from scratch, simple explanation and cool animation 👌 PS: you got a new subscriber More to go 🥰😍

I dont now how you could use something like this but i really like how much fun you have with this XD

This reminds me of getting in trouble for running a sieve of eratosthenes on university computers during my undergrad. Turns out it takes up a lot of computer resources if you just let it go. :) I'd highly recommend checking out 3b1b's video on prime visualizations (the one on prime spirals and Dirichlet's theorem), as it goes into a lot of the very cool maths behind this sort of stuff!

The tense music on the syntax is fire

your contents are insane

such a great vid

Amazing !

Mrs Richards: "I paid for a room with a view !" Basil: (pointing to the lovely view) "That is Torquay, Madam ." Mrs Richards: "It's not good enough!" Basil: "May I ask what you were expecting to see out of a Torquay hotel bedroom window? Sydney Opera House, perhaps? the Hanging Gardens of Babylon? Herds of wildebeest sweeping majestically past?..." Mrs Richards: "Don't be silly! I expect to be able to see the sea!" Basil: "You can see the sea, it's over there between the land and the sky." Mrs Richards: "I'm not satisfied. But I shall stay. But I expect a reduction." Basil: "Why?! Because Krakatoa's not erupting at the moment ?"

@krccmsitp2884

Жыл бұрын

Is that from Fawlty Towers? I love that show!

@fredflintstoner596

Жыл бұрын

@@krccmsitp2884 I KNOW NOTHING !

As mentioned in other comments, the isPrime() method, since you iterate through numbers 2 till your current number, it's a lot less process heavy when storing former primes into an array, since you have calculated them already, and composite numbers do not need to be checked as a modulo. The only reason when I would not do this is when programming C or assembly for microchips with limited storage, since often those aren't speed depending and are rather focused on optimizing memory. Also, It's kinda neat to see a spiral occur from a switch statement, since I personally have always stuck to for loops in similar situations. Very interesting videos, even though they're very simple, it's very relaxing too watch.

I love your videos! 😁

Those character animations are ready for their own streaming blockbuster series!!!

for precalculating primes in a boolean array, use the sieve of eratosthenes: en.wikipedia.org/wiki/Sieve_of_Eratosthenes. It is a fast way of comping the prime numbers starting from 2

@12Q46HPRN

2 жыл бұрын

I was thinking this just after he got to the sqrt() part. Since the number of primes calculated will be finite, even with a very large spiral, iteration over an array of found primes might be optimal in this case.

@MasterHigure

2 жыл бұрын

@@12Q46HPRN Optimal depending on what you mean. A full array uses much more memory than checking each time.

@12Q46HPRN

2 жыл бұрын

@@MasterHigure I was looking at speed. Checking an array of known primes for factors of n, and limiting the search to betwern 2 and sqrt(n) within that array was my thought. I'm always looking for a good-fit algorithm for prime-checking. What's your suggestion in this scenario?

@Vargol

2 жыл бұрын

An alternative take on the sieve if you've not got a fixed set is that you only need to test if a number its divisible by your previously found prime numbers up to n/2 as the non primes have already factored using other primes, so checking 17 only 2,3,5 and 7 would need to be checked as any thing that divides by 4, 6 and 8 divides by 2 and if you unnecessarily rounded up your n/2 and check 9 well anything that divides by 9 also divides by 3. That is how the sieve eliminates numbers from the fixed set.

@Wouldyoukindly4545

2 жыл бұрын

@@12Q46HPRN and by known primes, you can use the list of primes you have already built. Then add to it if you find it is prime.

This was really cool

A clean way to think about the spiral movement is with an immutable state like (dx, dy, currentStep, stepToTurn). When I say "immutable" I mean that you never modify a state but instead replace the entire thing on each transition. Consider (1,0,3,8). Transitioning to a new state simply adds one to the third element, (1,0,4,8). Turning is the complicated part: if the third element is equal to the fourth element, then instead of adding 1, reset the third to zero, swap the first two elements, and if the abs of the second element was 1, add 1 to the fourth element and multiply each of the first two elements by negative 1.

Here is a nice one to animate on this spiral with dots that are ON or OFF. - Start with all dots OFF. - Next, toggle all positions that are multiples of 1 (i.e. toggle everything ON for this case). - Then, toggle all positions that are a multiple of 2 (i.e. toggle all even numbers OFF again). - Then toggle all multiples of 3. - etc. - In step n, toggle all positions that are multiples of n. - repeat until nothing gets toggled anymore. You'll get a very distinct - almost boringly predictable - pattern of even clearer lines than in the Ulam case. But the intermediate steps start messy and then magically clean up quite nicely. Understanding why is rewarding in itself...

@TheCodingTrain

2 жыл бұрын

Hopefully I can give this a try on my next live stream!

Damn I wish you were my coding teacher in college or high school this seems a lot more fun and informative than the stuff they made us do

I was /just/ looking at algos to generate the square spiral yesterday. What a coincidence!