Runtime of optimized Primehunter
- by Setton
Ok so I need some serious runtime help here!
This method should take in an int value, check its primality, and return true if the number is indeed a prime. I understand why the loop only needs to go up to i squared, I understand that the worst case scenario is the case in which either the number is prime (or a multiple of a prime). But I don't understand how to quantify the actual runtime.
I have done the loop myself by hand to try to understand the pattern or correlation of the number (n) and how many loops occur, but I literally feel like I keep falling into the same trap every time. I need a new way of thinking about this!
I have a hint:
"Think about the SIZE of the integer"
which makes me want to quantify the literal number of integers in a number in relation to how many iterations it does in the for loop (floor log(n)) +1). BUT IT'S NOT WORKIIIING?! I KNOW it isn't square root n, obviously.
I'm asking for Big O notation.
public class PrimeHunter
{
public static boolean isPrime(int n)
{
boolean answer = (n > 1) ? true : false; //runtime = linear runtime
for (int i = 2; i * i <= n; i++) //runtime = ?????
{
if (n % i == 0) //doesn't occur if it is a prime
{
answer = false;
break;
}
}
return answer; //runtime = linear runtime
}
}
