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

Filed under:
|

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

Related posts about java

Related posts about big-o