Justin Robbins

Ranch Hand

Posts: 121

2

posted 1 year ago

Had this as an exam question and I was quite befuddled on how to solve.

Implement a method called prime that computes all prime numbers less than or equal or to the parameters passed to it (let us call it n) using the Sieve of Eratosthenes algorithm described below in pseudo-code:

1. Create an ArrayList called primeList and add 2 to it as the first prime number

2. For i between 3 and n

3. Set flag isPrime to true

4. For each integer j in primeList

5. If i is divisible by j set flag isPrime to false

6. End for each

7. If isPrime is true, add i to the primeList

8.End for

9. Return primeList

10. Fill in the body of the method below

public arraylist primesieve(int n){

}

Any steps would be greatly appreciated

Thank you

Implement a method called prime that computes all prime numbers less than or equal or to the parameters passed to it (let us call it n) using the Sieve of Eratosthenes algorithm described below in pseudo-code:

1. Create an ArrayList called primeList and add 2 to it as the first prime number

2. For i between 3 and n

3. Set flag isPrime to true

4. For each integer j in primeList

5. If i is divisible by j set flag isPrime to false

6. End for each

7. If isPrime is true, add i to the primeList

8.End for

9. Return primeList

10. Fill in the body of the method below

public arraylist primesieve(int n){

}

Any steps would be greatly appreciated

Thank you

posted 1 year ago

That's a rather misleading set of instructions. In real life you would want an array representing integers from 1 to N, which you go through repeatedly marking some as non-prime, and a list representing known primes found so far. Those instructions don't mention anything like that.

Try it with pencil and paper first.

Try it with pencil and paper first.

posted 1 year ago

I wouldn't say the instructions are misleading. Rather, they just describe an alternative approach to the usual boolean array. It's based on the fact that non-prime numbers are divisible by at least one smaller prime number. So, for each number you want to check, you'd iterate over the primes you have found so far, which are stored in the ArrayList, to see if any of them is a factor of the number being checked.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Campbell Ritchie

Marshal

Posts: 56553

172

Campbell Ritchie

Marshal

Posts: 56553

172