I also have a few general comments on your aglorithm.
1) To start with, your code formatting isn't very good, which makes it difficult to read. Code that appears in the same scope (i.e. the same depth of braces) should be indented the same amount. Also, class names (and also, therefore, constuctor names) should be capitialized. Following these conventions allows other progammers to more easily understand what each identifier IS. Sun has a good document that outlines conventions on identifier names, which you should check out.
2) You have done while(true). As a side effect, if you try to find TOO many prime numbers, you will end up overflowing your incrementation, giving you negative numbers, which is not what you want. So, you really should put a maximum cap on things. I would suggest using a "for loop", instead of a while loop, because adding that maximum means that you now are emulating all three specifiers for a for loop. So I would change your code to this:
public class PrimeNumber {
long i = 1; // this will be the incrementation variable used to find if a given number is prime
long number; // this is where I'm going to start searching for the nth prime number
long count = 2; // this is the ordinal for each prime number -- initialized to 2, because there are 2 prime numbers before 5 (the number I will start searching at)
public PrimeNumber() {
for (number = 5; number < Long.MAX_VALUE; number += 2) {
if (number % 2 != 0) {
for (i = 3; i < number; i += 2) {
if (number % i == 0) {
flag = true;
}
}
}
if (flag == false) {
count++;
}
if (count == 4) {
break;
}
flag = true;
}
}
}
next, I would recognize that the variable "i" will only be used within the for loop where it is assigned the value of 3, and incremented. So, I would move the definition of it into that loop, narrowing it's scope, so that it doesn't cause confusion as to it's purpose.
like this:
public class PrimeNumber {
long number; // this is where I'm going to start searching for the nth prime number
long count = 2; // this is the ordinal for each prime number -- initialized to 2, because there are 2 prime numbers before 5 (the number I will start searching at)
public PrimeNumber() {
for (number = 5; number < Long.MAX_VALUE; number += 2) {
if (number % 2 != 0) {
for (long i = 3; i < number; i += 2) {
if (number % i == 0) {
flag = true;
}
}
}
if (flag == false) {
count++;
}
if (count == 4) {
break;
}
flag = true;
}
}
}
Next, recognizing that this whole "flag" issue was the original problem, I would remember why I don't like "flags" in the first place. Instead, I would use an under-used language feature called "continue".
The purpose of your flag is to prevent count from incrementing if you discover that it is NOT a prime number. Instead, if you discover it's not a prime number, just DIRECTLY move onto checking the next number, like this:
public class PrimeNumber {
long number; // this is where I'm going to start searching for the nth prime number
long count = 2; // this is the ordinal for each prime number -- initialized to 2, because there are 2 prime numbers before 5 (the number I will start searching at)
public PrimeNumber() {
numUnderTest:for (number = 5; number < Long.MAX_VALUE; number += 2) {
if (number % 2 != 0) {
for (long i = 3; i < number; i += 2) {
if (number % i == 0) {
continue numUnderTest;
}
}
}
count++;
if (count == 4) {
break;
}
}
}
}
next, I recognize that the test of number % 2 != 0 is redundant, because we're starting with an odd number, and always adding 2, and disallowing overflow. So I remove it:
public class PrimeNumber {
long number; // this is where I'm going to start searching for the nth prime number
long count = 2; // this is the ordinal for each prime number -- initialized to 2, because there are 2 prime numbers before 5 (the number I will start searching at)
public PrimeNumber() {
numUnderTest:for (number = 5; number < Long.MAX_VALUE; number += 2) {
for (long i = 3; i < number; i += 2) {
if (number % i == 0) {// if this is never true for any i, only then will the code to increment count ever be reached.
continue numUnderTest;
}
}
count++;
if (count == 4) {
break;
}
}
}
}
Next, I notice that this doesn't scale -> if you try to find a prime number that is beyond the range of all longs (i know, it would take forever, but humor me) -> that is, you change count == 4 to count == some really high number, since we've disallowed overflow, you end up stopping prematurely, and getting the wrong result. Furthermore, if we had allowed overflow, you'd still get the wrong result -> it would, in fact, start giving you negative versions of numbers you already had, until it reached and passed zero, and started repeating numbers you already had. What you need to do if you ever don't find the one you're looking for, is throw an exception. So, instead of using "break" to exit the loop, use "return", so that if you ever exit the loop normally, you throw an exception. Like this:
public class PrimeNumber {
long number; // this is where I'm going to start searching for the nth prime number
long count = 2; // this is the ordinal for each prime number -- initialized to 2, because there are 2 prime numbers before 5 (the number I will start searching at)
public PrimeNumber() {
numUnderTest:for (number = 5; number < Long.MAX_VALUE; number += 2) {
for (long i = 3; i < number; i += 2) {
if (number % i == 0) {// if this is never true for any i, only then will the code to increment count ever be reached.
continue numUnderTest;
}
}
count++;
if (count == 4) {
return;
}
}
throw new Exception("Can't calculate that prime number - it's too large");
}
}
Okay, now I'm generally satisfied that the algo works the way you want it to, without using redundancy or flags.
So, now a word about your class structure. Using package protected variables doesn't really make sense in this case. I can't see any reason why you would want to prevent anybody not in your package from accessing the value of the prime number. Make number public. Next, look at count. It's got a bad scope. It's not accessed in any methods except the constructor, and doesn't need to be read by any public clients, so it should be a local variable.
Next, the line (count == 4) uses a "magic number" -> 4 is hard coded, and seemingly meaning less, unless you know why it is hard coded. You should make it a variable (possibly make it final to indicate that it won't change) and name it so that we know what you're doing with it. Also, for this class to really be useful, you don't want to hard code it, anyway. What you really want to do is allow it to be passed as a parameter, so that clients can choose which prime number they want. Furthermore, that really should be part of the state of the object -> what differentiates two prime numbers is their ordinal (their position in the sequence of prime numbers that starts at 2).
So, I would have something like this:
public class PrimeNumber {
public long number; // this is where I'm going to start searching for the nth prime number
public long ordinal; // this is the position of the number in the strictly ascending sequence of all prime numbers.
public PrimeNumber(long pos) {
long count = 2; // this is the ordinal for each prime number -- initialized to 2, because there are 2 prime numbers before 5 (the number I will start searching at)
numUnderTest:for (number = 5; number < Long.MAX_VALUE; number += 2) {
for (long i = 3; i < number; i += 2) {
if (number % i == 0) {// if this is never true for any i, only then will the code to increment count ever be reached.
continue numUnderTest;
}
}
count++;
if (count == pos) {
ordinal = pos;
return;
}
}
throw new Exception("Can't calculate that prime number - it's too large");
}
}
So, now we let the client specify which ordinal, then calculate that prime. If the prime can be found, it creates an object with that number. If not, and exception is thrown, and no object is ever created.
So, what's left? Well, what happens if client passes a parameter value for "pos" that is less than or equal to 2? I'll leave you to work out how to solve that, but basically, you've got valid cases for 1 and 2, and you've got invalid cases for anything else, which should throw illegalArgumentExceptions, probably.
My final comment is regarding you prime number algorithm itself. You are attempting to find out if it is divisible by ALL odd numbers lower than itself. You don't need to. There are two optimizations you can add:
1) If any number is divisible by a given factor, it yeilds a quotent. It is also divisible by that quotient, which yeilds the original factor. Furthermore, unless the factor is EXACTLY the squareroot of the number, then one of either the divisor or the quotient is LARGER than the square root and the other is SMALLER.
2) If a number is divisible by a composite number, it is also guaranteed to be divisible by all the factors of that number. Hence, if you check that it is divisible by the factors of that number, there is no need to check if it is divisible by that number. This leads to realizing that you only need to check if it is divisible by the prime factors of any given number.
If you put these two together, you realize that you could store the prime numbers as you find them in an array, and only check to see if the number you're testing is divisible by the prime numbers smaller than it's square root. For example, you don't need to test to see if it is divisible by 9, because if it is, it is also divisible by 3. This WILL require more memory, but as you start getting towards, say, 100001th prime number, it's going to save you a LOT of time.
- Adam
