Databases
StackOverflow2013
Postsdbo
POChecking if an int is prime more efficiently
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POChecking if an int is prime more efficiently
    primarykey
    data
    text
    <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>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USstarblue
    1. USSipSop
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTDuplicate
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POChecking if an int is prime more efficiently
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POChecking if an int is prime more efficiently
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POChecking if an int is prime more efficiently
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONote that for a problem such as this, the wide variety of answers can be combined in various ways.
      singulars
      1. POChecking if an int is prime more efficiently
      1. USoutis
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload