We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
For those interested:
If a number is divisable by another number less or equal to the square root of the first number... it is NOT prime. That is the reason for O(sqrt(n)) run time.
so:
for (i = 2; i*i <= n; i++){
//if divisible
if (n % i == 0)
NOT PRIME
}
remember that the number 1 is not prime (special case)
and you're done.
Day 25: Running Time and Complexity
You are viewing a single comment's thread. Return to all comments →
For those interested: If a number is divisable by another number less or equal to the square root of the first number... it is NOT prime. That is the reason for O(sqrt(n)) run time.
so:
remember that the number 1 is not prime (special case) and you're done.