Win a copy of Spring in Action (5th edition) this week in the Spring forum!
  • 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
Bartenders:
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

How many prime numbers in a given range  RSS feed

 
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

I'm trying to program something that will tell me how many prime numbers there is from 0 to 1000.


Would there be a simpler way ?
Thank you
 
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Emma,

you gave an implementation of the famous Sieve (of Eratosthenes). That is the simplest (and fastest) way I know. Maybe you could replace the multiplication by a summation, to get all the multiples, that will probably be just a little faster.

If you really want to make it easy on yourself: have a look at the BigInteger class, that has this method 'probablyPrime'. Believe it or not, but using a java 8 stream and this BigInteger, you would only need just one line of code!
 
Emma Vande-Wouwer
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you, I've had a look but haven't figured out how to use this BigInteger, I'll keep on trying.
Thanks again
 
Sheriff
Posts: 5446
147
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here are some comments on your code not related to the subject of the thread:

* The Java convention is to start a variable with a lowercase letter.
* final int Limit = Integer.parseInt("1000"); can be simplified to final int Limit = 1000;
* If you follow the convention, this code
would be written
* It's a good idea to get out of the habit of posting all your code in the main() method.  A standard template for this would look like this:
 
Saloon Keeper
Posts: 5140
54
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Knute Snortum wrote:* If you follow the convention, this code
would be written


These two loops are not the same. In this case "Limit" is inclusive so the second example won't work correctly unless Limit has been incremented by one prior to this section of code.
 
Knute Snortum
Sheriff
Posts: 5446
147
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the clarification.  Off-by-one errors are hard.
 
Piet Souris
Master Rancher
Posts: 3001
105
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Useful would be to make a method 'public static List<Integer> getPrimes(int limitInclusive)' that contains the code that is now in main. Then you can use it whenever you need it, with

Another way, interesting as a coding exercise, is that a number N is prime if it is not a multiple of any known prime number that is smaller than N. We know that 2 and 3 are primes, so we can start with a List<Integer> primes containing 2 and 3. Now, if a number N is not a multiple of any number in our List, then it is a prime number and can be added to the list, et cetera. It is certainly not as fast as the Sieve, but it makes for a short and elegant solution. Give it a try!
 
ice is for people that are not already cool. Chill with this tiny ad:
Download Free Java APIs to Work with Office Files and PDF
htttp://www.e-iceblue.com/free-apis.html
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!