posted 1 month ago

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

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

posted 1 month ago

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!

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

posted 1 month ago

Thank you, I've had a look but haven't figured out how to use this BigInteger, I'll keep on trying.

Thanks again

Thanks again

posted 1 month ago

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.

*

* 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:

* 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:

All things are lawful, but not all things are profitable.

posted 1 month ago

These two loops are not the same. In this case "Limit" is

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.

You have the right to remain sentient. If you give up the right to remain sentient,

you will be elected to public office.

posted 1 month ago

Thanks for the clarification. Off-by-one errors are hard.

All things are lawful, but not all things are profitable.

Piet Souris

Rancher

Posts: 2833

96

posted 1 month ago

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!

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. |