Some notes:
Your bracing does not follow standard Java conventions. This is more of a matter of preference, but this is how I would format your code:
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(2);
int count = list.size();
int number = 3;
while (count != 100) {
boolean isPrime = true;
for (int i = 0; i < list.size(); i++) {
if (number % list.get(i) == 0) {
isPrime = false;
}
}
if (isPrime) {
list.add(number);
}
number++;
count = list.size();
}
System.out.println(list);
Some other points about formatting:
- I have removed some excess blank spaces and lines.
- I put braces around all the statements inside the
if
statement without braces.
Now, to the loop:
while (count != 100) {
boolean isPrime = true;
for (int i = 0; i < list.size(); i++) {
if (number % list.get(i) == 0) {
isPrime = false;
}
}
if (isPrime) {
list.add(number);
}
number++;
count = list.size();
}
This could easily be a for
loop:
for (int count = 1, number = 3; count < 100; number++) {
boolean isPrime = true;
for (int i = 0; i < list.size(); i++) {
if (number % list.get(i) == 0) {
isPrime = false;
}
}
if (isPrime) {
list.add(number);
}
count = list.size();
}
Also, all your list.size()
. You can remove many of the calls:
for (int count = 1, number = 3; count < 100; number++) {
boolean isPrime = true;
for (int i = 0; i < list.size(); i++) {
if (number % list.get(i) == 0) {
isPrime = false;
}
}
if (isPrime) {
list.add(number);
count++;
}
}
You can also remove much of the iterations of the inner loop by break
ing when isPrime is true, or just:
for (int count = 1, number = 3; count < 100; number++) {
for (int i = 0; i < list.size(); i++) {
if (number % list.get(i) == 0) {
list.add(number);
count++;
break;
}
}
}
But the main thing is, your code is not as efficient as it could be. Try a Sieve:
List<Integer> result = new LinkedList<Integer>();
int n = 1.4 * 100 * Math.log(100);
boolean[] isPrimeArray = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
isPrimeArray[i] = true;
}
for (int i = 2, primesLeft = 100; i * i <= n && primesLeft > 0; i++) {
if (isPrimeArray[i]) {
result.add(i);
primesLeft--;
for (int j = i; i * j <= n; j++) {
isPrimeArray[i * j] = false;
}
}
}
System.out.println(result);
The sieve does:
- Sets all numbers to
true
(as in, is a prime).
- Starts at 2, and works its way through the primes. While doing that, marks all the multiples of a prime to
false
.
- If it has 100 primes, the loop will terminate.
- Print the result.
Also you have 100
as a magic number. Set it as a field:
private static final int MAX = 100;
// Code here
Use:
List<Integer> result = new LinkedList<Integer>();
int n = 1.4 * MAX * Math.log(MAX); // Overestimate by 40%
boolean[] isPrimeArray = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
isPrimeArray[i] = true;
}
for (int i = 2, primesLeft = MAX; i * i <= n && primesLeft > 0; i++) {
if (isPrimeArray[i]) {
result.add(i);
primesLeft--;
for (int j = i; i * j <= n; j++) {
isPrimeArray[i * j] = false;
}
}
}
System.out.println(result);
This will result in a much faster result.