title: Find a largest prime number less than n
body: <p>How can I find a largest prime number which is less than n, where  n ≤ 10¹⁸ ?
  Please help me find an Efficient Algorithm.</p>
  
  <pre><code>for(j=n;j&gt;=2;j--) {
    if(j%2 == 1) {
      double m = double(j);
      double a = (m-1)/6.0;
      double b = (m-5)/6.0;
      if( a-(int)a == 0 || b-(int)b == 0 ) {
        printf("%llu\n",j);
        break;
      }
    }
  }
  </code></pre>
  
  <p>I used this approach but this is not efficient to solve for n>10^10;</p>
  
  <p>How to optimize this..</p>
  
  <p><strong>Edit:</strong> 
  Solution: Use Primality test on each j. </p>
  
  <p><a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test" rel="nofollow">Miller Rabin</a>, <a href="http://en.wikipedia.org/wiki/Fermat_primality_test" rel="nofollow">Fermat's  Test</a>. </p>