Can you explain the for loop clearly, what we are trying to do and the intuition behind. Video is not clear and the instructor is also confused.
Explain the for loop in isPrime() function
looking for detailed explanation with example.
Hey @Jagrit
Basically after finding primes we are iterating over array of primes and checking if num is multiple of prime or not
If its multiple then we return false
for(int i=0;primes[i]*(long long)primes[i]<=n;i++) //if primes[i]^2 becomes greater than n then you will not find any prime which can be multiple of n since max multiple of n is sqrt(n)Okay. That is fine that we are checking whether its n is divisible by any prime. Can explain the proof behind this, that only checking whether the number is divisible by prime solves the issue?
Ok you can break any number as primes right i.e called prime factorisation of the number
So if its divisible by any prime then that means that prime is part of prime factorisation of that number hence its a composite num
Otherwise its a prime no
Okay okay. So any number can be divided into set of primes, like 14 can be 72, both are prime. or you can say 15 can be written as 53. Now I will only check if the given num is not divisible by any of the primes less than its sqrt, it means it will be not divisble by anything else. So its also a prime. Okay. I got it. So I can say that, to check if any number is prime, I only need to see if it is divisible by any of its prime factors? Is it right?
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.