title: Checking if an int is prime more efficiently
body: <p>I recently was part of a small java programming competition at my school. My partner and I have just finished our first pure oop class and most of the questions were out of our league so we settled on this one (and I am paraphrasing somewhat): "given an input integer n return the next int that is prime and its reverse is also prime for example if n = 18 your program should print 31" because 31 and 13 are both prime. Your .class file would then have a test case of all the possible numbers from 1-2,000,000,000 passed to it and it had to return the correct answer within 10 seconds to be considered valid. </p>
  
  <p>We found a solution but with larger test cases it would take longer than 10 seconds. I am fairly certain there is a way to move the range of looping from n,..2,000,000,000 down as the likely hood of needing to loop that far when n is a low number is small, but either way we broke the loop when a number is prime under both conditions is found. At first we were looping from 2,..n no matter how large it was then i remembered the rule about only looping to the square root of n. Any suggestions on how to make my program more efficient? I have had no classes dealing with complexity analysis of algorithms. Here is our attempt. </p>
  
  <pre><code>public class P3
  {
  
     public static void main(String[] args){
  
      long loop = 2000000000;
      long n = Integer.parseInt(args[0]);
      for(long i = n; i&lt;loop; i++)
      {
        String s = i +"";
        String r = "";
        for(int j = s.length()-1; j&gt;=0; j--)
          r = r + s.charAt(j);
        if(prime(i) &amp;&amp; prime(Long.parseLong(r)))
        {
            System.out.println(i);
            break;
        }
      }
      System.out.println("#");
    }
  
    public static boolean prime(long p){
  
  
  for(int i = 2; i&lt;(int)Math.sqrt(p); i++)
      {
        if(p%i==0)
          return false;
      }
      return true;
    }
  }
  </code></pre>
  
  <p>ps sorry if i did the formatting for code wrong this is my first time posting here. Also the output had to have a '#' after each line thats what the line after the loop is about Thanks for any help you guys offer!!!</p>