• 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:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

How many prime numbers in a given range  RSS feed

 
Greenhorn
Posts: 8
  • 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
 
Rancher
Posts: 2833
96
  • 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: 8
  • 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: 5124
138
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: 4765
52
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: 5124
138
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
Rancher
Posts: 2833
96
  • 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!
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!