Databases
StackOverflow2013
Postsdbo
POWhy does this prime checker work, and not work if I try to make it more efficient
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy does this prime checker work, and not work if I try to make it more efficient
    primarykey
    data
    text
    <p>Below is one of the first programs I made (with help from the Internet) in Java. It is a program that checks if a given integer is prime or not and prompts the user with feedback. If the user input is not an integer it outputs that it is not an integer. The latter also happens when Big Integers are entered. This is the code:</p> <pre><code>import java.util.Scanner; class BasicPrime1 { public static void main(String[] args) { try { System.out.println("Enter an Integer: "); Scanner sc = new Scanner(System.in); int i; int number = Integer.parseInt(sc.nextLine()); // 1 and numbers smaller than 1 are not prime for (i = 1; number &lt;= i;) { System.out.println("NOT a prime!"); break; } // Number is not prime if the remainder of a division (modulus) is 0 for (i = 2; i &lt; number; i++) { int n = number % i; if (n == 0) { System.out.println("NOT a prime!"); break; } } // I do not understand why the if-statement below works. if(i == number) { System.out.println("YES! PRIME!"); } } catch(NumberFormatException nfe) { System.out.println("Not an integer!"); } } } </code></pre> <p>This program does his job, but I do not know why the part with the if-statement works. <strong>How is it possible that "i == number" gives a value of true</strong> (it prints out "YES! PRIME" when you enter a prime)? The local variable i gets incremented in the for-loop, but the if-statement is outside of the for-loop.</p> <p><strong><em>/edit</strong> the paragraph below is nonsense as <a href="https://stackoverflow.com/questions/18391768/why-does-this-prime-checker-work-and-not-work-if-i-try-to-make-it-more-efficien/18391919#18391919">Jim Lewis points out</a></em><br> <strike>Thinking about it now, the only reason I can think of that this is the case is because the == operator checks if the i-'object' and number-'object' belong to the same 'type' (i.e., have a reference to the same object). Since they both belong to the type of primitive integers this program catches the integers (other input throws a NumberFormatException which is caught and outputs "Not an integer"). The ones that are primes pass the first for-loop and then the magical if-statement gives "true" and it prints out "YES! PRIME!".</strike></p> <p>Am I on the right track?</p> <p>I have improved this program by removing the magical if-statement and changing it for an if-else-statement like this: (<strong><em>/edit</strong> fixed problem with code thanks to <a href="https://stackoverflow.com/questions/18391768/why-does-this-prime-checker-work-and-not-work-if-i-try-to-make-it-more-efficien#comment27011860_18391768">answer of ajb</a></em>)</p> <pre><code>boolean factorFound = false; for (i = 2; i &lt; Math.sqrt(number) + 1; i++) { int n = number % i; if (n == 0) { factorFound = false; break; } else { factorFound = true; } } if(factorFound == false) System.out.println("NOT a prime!"); if(factorFound == true) System.out.println("YES! PRIME!"); </code></pre> <p>By only going up to the square root of the input number the calculation time improves (I know it can be even more improved by only checking odd numbers or using a <a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="nofollow noreferrer">AKS Primality Test</a>, but that is beside the point).</p> <p>My main question is why I could not improve the efficiency of the first program (with the magical if-statement) in the same manner. When I enhance the for-loop like this "(i = 2; i &lt; Math.sqrt(number) + 1; i++)" in the first program it does no longer print out "YES! PRIME!" when you input a prime. It gives a blank. Even if my previous explanation is correct - which it is probably not - this is not explained. </p> <p>You may enlighten me.</p> <p>ANSWER: <a href="https://stackoverflow.com/questions/18391768/why-does-this-prime-checker-work-and-not-work-if-i-try-to-make-it-more-efficien/18391919#18391919">int i is outside of scope of for-loop and after going through the for-loop multiple times upto number the value of i will reach the value number, when we can be sure it is a prime</a>. Furthermore, after checking the disappearing "YES! PRIME!" statement once again it turns out it is actually possible to change number in both the if-statement and for-loop to ( Math.sqrt(number) + 1 ) and have working code. So the question was based on a false premise. </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USErwin Rooijakkers
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhy does this prime checker work, and not work if I try to make it more efficient
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIn the second example, you're not letting it go through the entire loop. If n is 0, then you know it's not prime and you can quit the loop right now, which is correct. But if n isn't 0, you have to go through the loop again, but the way you've coded it, you're breaking out. You need to keep going through the loop, and then when the loop is done, you check whether you left because you found it wasn't prime, or whether the whole loop finished. The best way is to define a boolean, say `factorFound`; initialize it to false, set it to true before breaking, and test it after the loop is done.
      singulars
      1. POWhy does this prime checker work, and not work if I try to make it more efficient
      1. USajb
    2. COAh you are right. If number % i is non-zero that does not mean that there is not another higher i for which it is zero, and thus the second example can give false positives. I updated the code with a boolean and now it works properly.
      singulars
      1. POWhy does this prime checker work, and not work if I try to make it more efficient
      1. USErwin Rooijakkers
 

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