• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Implement a method that computes all prime ≤ to the parameters passed to it?

 
Ranch Hand
Posts: 121
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Marshal
Posts: 28257
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Sheriff
Posts: 17652
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Marshal
Posts: 79392
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That is the procedure used in the Sieve of Eratosthenes, but taken backwards.
 
Sheriff
Posts: 7125
184
Eclipse IDE Postgres Database VI Editor Chrome Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What specifically are you having trouble with?
 
Campbell Ritchie
Marshal
Posts: 79392
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
if it was for an exam, what did you write? Are you aware of this class?
 
Try 100 things. 2 will work out, but you will never know in advance which 2. This tiny ad might be one:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic