Check If A Number Is Prime Using Recursion | C Programming Example

[@justcurious1940]

Great video Kevin, we can actually use a static or a global variable to solve this, but I think it's not recommended,because some weird bugs may show up if u try to call the function using a loop. _Bool prime_recursive(int x){ static int ii = 2; if(x= x/2){ return true; } else{ ++ii; prime_recursive(x); } }

[@dankodnevic3222]

If you have a wrapper function, limit for 'i' should be (int) floor(sqrt(0.0+n)) , not n/2

[@PortfolioCourses]

What is in the video is correct. :-) What you are suggesting is a further optimization that we could make. There are many other optimizations we could make. But this video is for beginners that are mostly new to programming that will be searching for a solution to this problem, so it’s been kept simpler. We don’t need a wrapper function to make that optimization.

[@dankodnevic3222]

@@PortfolioCourses I understand that you simplify solutions for beginners, but in that case you could sweep the hole range 2..n, because n/2 doesn't mean anything in this case. For me, wrapper looked like a trigger for optimization. The simplest one was to sweep while ((i*i)

[@PortfolioCourses]

So I hear you, but you’ll find virtually all beginner textbooks and resources use n/2 because it’s considered simpler. I appreciate your feedback but saying “not” to use n/2 is incorrect, to be clear, three is nothing wrong with using n/2 for anyone reading this. If we want to do optimal checking of prime numbers that’s really a whole other problem with many, many optimizations we can make.

[@dankodnevic3222]

@@PortfolioCourses First, I want to apologize myself if I missed that n/2 in textbooks. I was triggered by your previous amount of hard work to make your clips almost perfect. That was fascinating for me in many occasions. That's why I recommend your channel, not just for beginners, but for seasoned programmers wishing to recover some old lessons. Something like a Yellow duck paradigm. I wish you much more subscribers. You deserve them!!!

[@PortfolioCourses]

Thank you for the kind words and support, I really appreciate it. :-) And thanks for suggesting the optimization, that's great to share as well.

[@gottod6895]

I believe the iterative approach is less complex and easier to understand and implement at least for me: and it also comes with O(n) linear time complexity. #include #include bool is_prime_iterative(unsigned int n) { if ( n 1 ; i-- ) if ( n % i == 0 ) return false; return true; } if C prefers recursion, does that mean that the recursive function is more performant that the iterative one ? I am new to programming btw.

[@PortfolioCourses]

I agree it's simpler to solve the problem with iteration (i.e. a loop), a video covering that approach is available here: kzbin.info/www/bejne/onLUeWWaqZyaa6s. I had some folks asking for a video covering how to solve the problem with recursion. :-) C doesn't really "prefer recursion", in general it's better to use iteration, though recursion can be useful to write easier to understand/read code when working on divide and conquer algorithms (types of algorithms that involves splitting a problem up into smaller pieces), as well as some data structures too (like trees).

[@unLinuxeroMas]

maybe this is too much to ask but a graphics way to explain this with squares and shapes would be very helpull to understand how this function works

[@mychaelwunnam7893]

thanks for the explanation

[@PortfolioCourses]

You’re welcome! :-)

[@DANMATHEWGAMALE]

what is the time complexity of this code?

[@PortfolioCourses]

Linear time complexity, the function essentially calls itself “n times” (practically n-2). :-)

[@DANMATHEWGAMALE]

@@PortfolioCourses thanks for the quick response sir, keep up those good content 🫡

[@PortfolioCourses]

@@DANMATHEWGAMALE You're welcome, I'm glad you enjoy the content! 🙂