Skip to content

Commit 57bccb7

Browse files
authored
Update _204.java (fishercoder1534#70)
1 parent 51c21e0 commit 57bccb7

File tree

1 file changed

+3
-1
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+3
-1
lines changed

src/main/java/com/fishercoder/solutions/_204.java

+3-1
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,9 @@ private boolean isPrime(int num) {
4848
But don't let that name scare you, I promise that the concept is surprisingly simple.
4949
5050
Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0.
51-
We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off.
51+
We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2 must not be primes, so we mark
52+
them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not
53+
be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off.
5254
What does this tell you? Should you mark off all multiples of 4 as well?
5355
4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off.
5456
So we can skip 4 immediately and go to the next number, 5.

0 commit comments

Comments
 (0)