title: Check if prime big-o
body: <p>My original function to determine if a number was prime was:</p>
  
  <pre><code>bool is_prime(int x) {
      for (int y = 2; y &lt; x; ++y) {
          if (x % y == 0) {
              return false;
          }
      }
      return true;
  }
  </code></pre>
  
  <p>This ran with a complexity of <code>O(x)</code> as you may have had to go to <code>x</code>.</p>
  
  <p>I've learned of some optimizations and need a check on my big-o. Here is the improved program:</p>
  
  <pre><code>bool is_prime(int x)
  {   
      if (x % 2  == 0 &amp;&amp; x &gt; 2) {
          return false;
      }
      for (int y = 3; y*y &lt;= x; y += 2) {
          if (x % y == 0) {
              return false;
          }
      }
      return true;
  }
  </code></pre>
  
  <p>Does the fact that I am now going up to the <code>sqrt()</code> change this to <code>O(sqrt(x))</code>?</p>