# Finding prime numbers

S Gregg

Greenhorn

Posts: 15

posted 5 years ago

I am stuck and looking for some guidance with this problem. I have researched and found solutions to this problem online but none of them work for me. I need to implement a single method that is going to have an int x passed to it. The method will need to check all values between 2 and x and then print all the prime numbers that fall between this range. For example

I have tried to implement methods I found into my problem but they don't work. Most of the methods I found use two methods to solve or just use a boolean to return if the value passed is prime or not.

Here is what I have so far, thank you very much for any help offered, it is greatly appreciated.

calcPrimeNumbers(28) would output

The primes less than or equal to 28 are:

2 3 5 7 11 13 17 19 23

I have tried to implement methods I found into my problem but they don't work. Most of the methods I found use two methods to solve or just use a boolean to return if the value passed is prime or not.

Here is what I have so far, thank you very much for any help offered, it is greatly appreciated.

posted 5 years ago

The inner condition is wrong...

If you find a divisor, then obviously, it isn't a prime... and yes, you need to check the next count. However, just incrementing the count isn't going to do it, you need to also jump to the next iteration of the while loop, in order to process the count.

If you don't find a divisor, with one iteration of the inner loop, that doesn't mean that it is a prime -- as you do in your condition. You need to fail the test for all iterations of the inner loop before it is considered a prime.

Henry

If you find a divisor, then obviously, it isn't a prime... and yes, you need to check the next count. However, just incrementing the count isn't going to do it, you need to also jump to the next iteration of the while loop, in order to process the count.

If you don't find a divisor, with one iteration of the inner loop, that doesn't mean that it is a prime -- as you do in your condition. You need to fail the test for all iterations of the inner loop before it is considered a prime.

Henry

Kurt Van Etten

Ranch Hand

Posts: 98

posted 5 years ago

Finding all the primes up to some input value would be a natural fit with using the Sieve of Eratosthenes. If you Google that you should find lots of references online. There was also a thread about it a couple of weeks ago right here in this forum.

Vinod Vinu

Ranch Hand

Posts: 217

posted 5 years ago

Same question here, i'm also stuck in this to find the prime nos.

What i'm assuming is that if the no. provided is greater than 1 than '2' itseld will be stored in a list to be displayed later to the user as a series of prime and if the no. given is either 0 or 1 then the list is null and hence no prime nos exists.

Following are the code:-

I got stuck in the logic. Right now i'm passing 10 in the construtor so the looping will be done as

2,3,4,5,6,7,8,9,10

The prime nos in the series are

But please give me some hint how can i check in the

Thanks alot.

What i'm assuming is that if the no. provided is greater than 1 than '2' itseld will be stored in a list to be displayed later to the user as a series of prime and if the no. given is either 0 or 1 then the list is null and hence no prime nos exists.

Following are the code:-

I got stuck in the logic. Right now i'm passing 10 in the construtor so the looping will be done as

2,3,4,5,6,7,8,9,10

The prime nos in the series are

2,3,5,7

But please give me some hint how can i check in the

**if**condition while iterating in**for loop**that the current index value is a prime or not and then put it in the list.Thanks alot.

Vinod Kumar Nair

"Any fool can write code that a computer can understan. Good programmers write code that humans can understand."

Bobby Smallman

Ranch Hand

Posts: 107

posted 5 years ago

You will be interested in reading through this past forum thread as well.

http://www.coderanch.com/t/516856/java/java/Sieve-Eratosthenes#2343984

http://www.coderanch.com/t/516856/java/java/Sieve-Eratosthenes#2343984

Everyday in every way, we get a little better.

Vinod Vinu

Ranch Hand

Posts: 217

posted 5 years ago

Just provide in your simple language. Don't post such complex links.

said by BobbyYou will be interested in reading through this past forum thread as well.

http://www.coderanch.com/t/516856/java/java/Sieve-Eratosthenes#2343984

Just provide in your simple language. Don't post such complex links.

"Any fool can write code that a computer can understan. Good programmers write code that humans can understand."

Campbell Ritchie

Sheriff

Posts: 50258

79

posted 5 years ago

Since there was a lot more than only Sieve of Eratosthenes in that discussion (I remember it well ), it is worth doing a search of javaRanch.Bobby Smallman wrote:. . . past forum thread as well. . . .

Bobby Smallman

Ranch Hand

Posts: 107

posted 5 years ago

Since it sounds like you want to avoid more complex code like the Sieve. A simple yet efficient way to do it is something along the lines of this

And if your end goal was providing a list of prime numbers and not just determining if a number was prime, you can clearly use that isPrime method that way as well. I got in the habit of breaking out small chunks of code like this for Project Euler.

The Sieve can speed things up but as you have pointed out it can be overwhelming when you are new to thinking about this kind of logic. It is important to note in the isPrime method there that it only goes to the sqrt of the number looking for divisors. That is a significant speed increase at least over iterating all the way through the number.

And if your end goal was providing a list of prime numbers and not just determining if a number was prime, you can clearly use that isPrime method that way as well. I got in the habit of breaking out small chunks of code like this for Project Euler.

The Sieve can speed things up but as you have pointed out it can be overwhelming when you are new to thinking about this kind of logic. It is important to note in the isPrime method there that it only goes to the sqrt of the number looking for divisors. That is a significant speed increase at least over iterating all the way through the number.

Everyday in every way, we get a little better.

Campbell Ritchie

Sheriff

Posts: 50258

79

Bobby Smallman

Ranch Hand

Posts: 107

posted 5 years ago

The Sieve is absolutely a significantly more efficient way to go. After already suggesting they research the Sieve further and read through a past post which showed the general outline of the Sieve and some pitfalls/optimizations which are helpful there was a comment that it was complex and to keep it simple. The method in my last post is an implementation of a non-Sieve method of finding prime numbers, I posted it as a stepping stone in their logic, because it is closer to their current code, to help them build a foundation in that sort of logic in order to ultimately be able to revisit their research in the Sieve.

With that being said, hopefully it is clear to the original poster that the Sieve of Eratosthenes make prime finding happy.

Campbell Ritchie wrote:The Sieve is hardly more complicated, and much more efficient; that code will run in quadratic time and looks inefficient to me.Bobby Smallman wrote:. . . A simple yet efficient way . . .

I suspect the Sieve is quadratic complexity, too, but still much faster.

The Sieve is absolutely a significantly more efficient way to go. After already suggesting they research the Sieve further and read through a past post which showed the general outline of the Sieve and some pitfalls/optimizations which are helpful there was a comment that it was complex and to keep it simple. The method in my last post is an implementation of a non-Sieve method of finding prime numbers, I posted it as a stepping stone in their logic, because it is closer to their current code, to help them build a foundation in that sort of logic in order to ultimately be able to revisit their research in the Sieve.

With that being said, hopefully it is clear to the original poster that the Sieve of Eratosthenes make prime finding happy.

Everyday in every way, we get a little better.

posted 5 years ago

You guys should realize that by now, the original poster has copied the inefficient code you gave, copy-pasted it, and handed it in for his homework assignment. He won't be back, and he didn't learn anything.

*Please*don't post working code examples, especially in this kind of thread; remember the adage regarding lifelong piscatorial pursuits.
Campbell Ritchie

Sheriff

Posts: 50258

79

Bobby Smallman

Ranch Hand

Posts: 107

posted 5 years ago

My bad At least I can be comforted by the knowledge that if that wonderfully intelligent/moral/scrupulous/Java loving/Insert other sarcastic adjectives here, did just copy/paste. He will be stuck with terribly weak code and no understanding of what should have been their goal of the thread. Won't happen again guys!

Everyday in every way, we get a little better.