Runtime of optimized Primehunter
Posted
by
Setton
on Stack Overflow
See other posts from Stack Overflow
or by Setton
Published on 2013-10-20T03:16:37Z
Indexed on
2013/10/20
3:54 UTC
Read the original article
Hit count: 122
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
}
}
© Stack Overflow or respective owner