title: Runtime of optimized Primehunter
body: <p>Ok so I need some serious runtime help here!</p>
  
  <p>This method should take in an int value, check its primality, and return <code>true</code> if the number is indeed a prime. I understand why the loop only needs to go up to <code>i</code> 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.</p>
  
  <p>I have done the loop myself by hand to try to understand the pattern or correlation of the number (<code>n</code>) 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!</p>
  
  <p>I have a hint:</p>
  
  <blockquote>
    <p>"Think about the SIZE of the integer"</p>
  </blockquote>
  
  <p>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 (<code>floor log(n)) +1</code>). BUT IT'S NOT WORKIIIING?! I KNOW it isn't square root <code>n</code>, obviously.</p>
  
  <p>I'm asking for Big O notation.</p>
  
  <pre><code>public class PrimeHunter 
  {
  
      public static boolean isPrime(int n)
      {
          boolean answer = (n &gt; 1) ? true : false; //runtime = linear runtime
  
          for (int i = 2; i * i &lt;= n; i++) //runtime = ?????
          {   
              if (n % i == 0) //doesn't occur if it is a prime
              {
                  answer = false;
                  break;
              }
  
          }
          return answer; //runtime = linear runtime
      }
  }
  </code></pre>