Coding Challenge 167: Ulam Spiral of Prime Numbers
Vložit
- čas přidán 3. 07. 2024
- 💻 Code: thecodingtrain.com/challenges...
✨ Watch the uncut version on Nebula! nebula.tv/videos/codingtrain-...
✨ Watch this video ad-free on Nebula! nebula.tv/videos/codingtrain-...
Why do prime numbers show up as diagonals in a spiral? In this video, I create a visualization in JavaScript (p5.js) of the Ulam Spiral (aka Prime Spiral) named for Polish Mathematician Stanislav Ulan.
p5.js Web Editor Sketches:
🕹️ Prime (Ulam) Spiral: editor.p5js.org/codingtrain/s...
🕹️ Number Spiral: editor.p5js.org/codingtrain/s...
🕹️ Prime vs Random Spiral: editor.p5js.org/codingtrain/s...
🕹️ Shapes & Color: editor.p5js.org/codingtrain/s...
🕹️ Incorporating 3D: editor.p5js.org/codingtrain/s...
🎥 Previous video: • Coding Challenge 166: ...
🎥 Next video: • Coding Challenge 168: ...
🎥 All videos: • Coding Challenges
References:
📺 CodingTrainChooChoo on Twitch: / codingtrainchoochoo
2️⃣ Mathematical Games: The remarkable lore of the prime numbers (1964): www.scientificamerican.com/ar...
📓 An Observation on the Distribution of Primes, M. Stein and S. M. Ulam: doi.org/10.2307/2314055
🗄 Prime Numbers (Wikipedia): en.wikipedia.org/wiki/Prime_n...
🗄 List of Prime Numbers: en.wikipedia.org/wiki/List_of...
🔗 Download Processing 4: processing.org/download
Videos:
🎥 Prime Spirals: • Prime Spirals - Number...
🎶 Processing Theme Selector music by / willfromamerica
Timestamps:
0:00 Welcome! Choo choo!
0:23 History of the Ulam Spiral
1:16 Diagramming the Spiral
2:18 Starting to Code
3:25 How and when do I rotate?
4:25 Coding the number spiral
7:00 Debugging!
9:40 Visualizing the spiral
12:22 What is a prime number?
14:31 Code to check if a number is prime.
18:57 Marking primes in the spiral
19:40 Porting to Processing (Java)
22:46 More references & examples
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: thecodingtrain.com/discord
💖 Membership: czcams.com/users/thecodingtrainjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#primenumbers #p5js #javascript
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.
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.
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
1/log(n) prime number theorum
@@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)
Sieve of Eratosthenes
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!
Thank you for this kind feedback!!
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
@@dinoswarleafs Me too except I'm two years behind
Tbufv
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
18:50 you picking out 2137 randomly out of all prime numbers hit me like a bag of bricks
Go on?
@@SleepyHarryZzz Polish meme. Pope jp2 died at 21:37
i see that im not the only one
While I appreciate all the machine learning videos, I really like simpler ones too: some cool math and fun visualizations. Loved this one!
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.
Simple yeah right. Im just fcking retarded. Hate my life.
O nie! Coding Train wybrał papieżową liczbę o 18:53, to znak :D
Boży kontent!
Piękne
: OOOO
I do tego sama spirala została wymyślona przez Polaka o:
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.
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.
I came to the comments to post exactly this!
@@englishish happy to see that someone thought the same way I did 😘
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).
@@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'.
@@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 love these simple coding challenges!! So informative.
Super glad to hear!
@@TheCodingTrain Coding challenges is how I found the channel and its still my favorite part! Thank you for still doing these!!
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)
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!
Wow, I love hearing this story!!
Wow I was about to comment my story which is very similar! His videos started my interest too, he’s a great guy
@@ledues3336 Keep these stories coming! 🚂❤️
me either, after I've learned nature of code from college, I changed my field from digital art to programming
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.
Well, that's a lovely way of implementing this!
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.
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!
Thank you! The code for these is also included!
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
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 < value
Well, unless i^2 becomes to big for its underlying data type, of course.
Yes, great tip!
just use sieve of eratosthenes
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;)
@@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.
man, your enthusiasm is great
Prime numbers are amazing, there is always something to learn from them
I love that the coding challanges are back!
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.
Awesome stuff as usual. Hadn't seen the Theme Selector in Processing *or* that you can execute functions from the console. So cool!!
Super glad to hear!
That was cool af
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)
@@Rolembeek33 Maybe come and ask for help in the coding train discord? thecodingtrain.com/discord
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.
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
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.
Whenever I'm feeling the effects of the impostor syndrome I watch a coding video on CZcams and my confidence returns.
i love the new direction this channel is going, the editing work is fabulous
You motivates me so much! Love your work!!
Great
Been watching u since forever, love ur vids so much
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 am loving the animations.
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.
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 THIS CHANNEL WOOOOWW Keep going!
I loved your video, it’s great content you’re showing. Keep it up ❤
I didn't knew that we can make such things with code, huge thank you !
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! ♥️
Appreciate the kind feedback!
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. :)
Welcome back!
I grew up watching you....Thanks for all the knowledge you shared❤️
ありがとう御座います。
とてもいい勉強になりました！
これを参考にして、
私の求めていた答えが一歩でも、
近づけるような気がします!
応用してみます！
As always, 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.
it always so fascinating to seeing how you reasoning
Hello sir, you have truly inspired me to code and are the reason I have learned machine learning.
I love the post-processing animations!
Man that was really cool. Thanks!
Theme selector for processing is just... AMAZING
Great lesson, love the added visuals!
Your videos always inspire me to try new things!
I just recently found this channel and I just wanna say I love this channel :D
Thanks for these videos, really great.
Thats fantastic
i didnt undertand 99% of this but i sat through every second of the video lol youre a natural born teacher my friend
You are so relatable with all the happy little accidents during coding. ☺️
I love you, Mr. Coding Train! You are far out, man.
dude, this is amazing. thanks 😄
fire content homie!
your contents are insane
I just love watching these videos. Thank you for these incredible videos
Appreciate it!!
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.
I swear your channel is my new favorite. I am gonna come by sometime on the stream and say hi.
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!!
Wow, I love hearing this story, thank you!
such a great vid
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.
This was really cool
Amazing content, thank you!
The animations are one point lately. Thanks for the content, such a fun channel.
I love your videos! 😁
love ur content
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!😍
Wow, I love hearing this story!!
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.
Ah, thank you, I will try this!
oh.my.god i love the coding challenges😍
Amazing, thanks for creating these!
Thanks for watching!
Your channel is gold sir
The tense music on the syntax is fire
That was a cool introduction to Javascript and Java! Very cool :)
Dude, love the concept. Teaching but hidden under a friend-youtuber type of video. Amazing
truly beautiful!,i've stared at this for 24:12 minutes.
I dont now how you could use something like this but i really like how much fun you have with this XD
Amazing !
You're just the best, and i need your source of ideas
Thank you
Very hopeful
23:10 waiting inpatiently for this! Great video absolutely love your energy
Great Job Dan.
Thank you!!
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.
i loved your video
Such a great explanation and that debugging session were so fun :D. Thanks for creating these types of videos...you are great!
Appreciate the kind feedback!
Woow, amazing channel, so much to learn.. thank you !
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.
Ooooh. Great suggestion!!
@@TheCodingTrain Thanks. I appreciate your appreciation.
😁
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 :)
@@johannes8144 What is the sieve of Erastosthenes?
@@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
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
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.
Thanks!
Thank you for the support!
I was /just/ looking at algos to generate the square spiral yesterday. What a coincidence!
CZcams 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 🥰😍
it’s so funny when u correct your mistakes
The miller-rabin primality test is a pretty nice one, and makes a lot of sense for anyone who knows modular arithmetic!
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.
man, you look so different yet similar to when you made the coding challenge #1
Love the content man, keep going!
It's been almost 6 years!!!
@@TheCodingTrain Time flies doesn't it?
😅
Those character animations are ready for their own streaming blockbuster series!!!
I have no background in coding..yet this was really fun to watch haha will come back for more
did that challenge last year using p5 js. Still fun to watch!
Please share yours!
@@TheCodingTrain Created PR just now
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
Not sure why this popped up in my recommended but I like it.