I am stuck on this beginner question:

a)Write a method that determines whether a number is prime. (I can do this part.)

b)Use this method in an application that determines and displays all the prime numbers less than 10,000. How many numbers up to 10,000 do you have to test to ensure that you have found all the primes?

I can't see how you would know you had found all the primes without testing each and every number.

Any tips?

Thanks

- 1

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

S Connor wrote:I'm just thinking there needs to be a way to record which numbers are not prime.

How about using a Set ?

I agree. Here's the better link: Salvin.in

I agree. Here's the better link: Salvin.in

- 1

The second part of the assignment demands to use that method to find all the primes up to 10.000.

Now, does that look like the Sieve being the goal of this assignment? I have my doubts.

@OP:

can you tell us what method you used in part 1?

Piet Souris wrote:..Now, does that look like the Sieve being the goal of this assignment? I have my doubts...

Interesting find ! I was diverted by the title of the post. Here's a cow.

However, it would not so optimal to do that 10,000 times

I agree. Here's the better link: Salvin.in

Indeed, the method of part 1 might be a little unhandy for part 2. That's why I am very anxious to know what method OP uses for part 1!

Suppose you have a method called helper taking two parameters: a List<Integer> primesFoundSofar, and a List<Integer> numbersNotYetChecked.

Now, we may assume that the first element of 'numbersNotYetChecked' is a prime (that is the basis for the Sieve). So we can add that first element to the first List (auch: I'm recording the primes!). Next, we can filter out all the multiples of that first element from numbersNotYetChecked. (I used a stream().filter(...) for this). Now we can enter the recursion. But what would be a stopping condition that prevents from going into an infinite recursion, and how do we start this recursion?

But again: that method is probably not what you have for part 1. You wrote that you had solved part 1. Can you show us that method?

S Connor wrote:Thanks for the advice. I am following an exercise book which ...

Thanks for mentioning the source, it would help us help you better if you provided the exact problem as stated in the book. As Piet pointed out, depending on the way in which your question is framed, the algorithm and code will change accordingly. As you probably understood, there is an elimination method that simply takes an upper bound and eradicates all numbers which are not prime, thus leaving behind the prime numbers. The actually way of determining that a single number is prime would be to ensure that is not divisible by a number less than it's square root.

S Connor wrote:I'm wondering if there is an elegant solution that does not require recording of which numbers are prime?

This is the simplest solution as mentioned above to test each number individually. But as you understood probably, it's not an optimal one if you want to repeat the same process over and over again for each number.

I agree. Here's the better link: Salvin.in

I am confused by this question. I have quoted the exact question in my post above. 'How many numbers up to 10,000 do you have to test to ensure that you have found all the primes?'

Well it seems to me that you have to test all the numbers up to 9973 to ensure that you have found them all. But how would you translate this into code?

S Connor wrote:'How many numbers up to 10,000 do you have to test to ensure that you have found all the primes?'

Well it seems to me that you have to test all the numbers up to 9973 to ensure that you have found them all. But how would you translate this into code?

Again, this seems to hint at the Sieve of Eratosthenes. Did you study the algorithm as it has been described? Why do you think the loop only goes up to square root of N as its upper limit, why not N? This means that if you use the Sieve of Eratosthenes algorithm for primes up to 10,000, you're only going to check 100 numbers at most.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

S Connor wrote:Here is my solution to the first part of the problem...

Before we dive into your solution .. let me point out a few things:

1. Your indentations are a bit messed up. Please use proper indentations for readability.

2. You have a method called "findPrimes". This name does not convey that it's restricted to 10000, it does not "find" anything, rather it prints numbers. Does it justify your method name ?

3. What is "p" ?

4. Lets assume n=10, when the loop for "a" runs the first time, it finds that 10 is divisible by 2. There is no need to go further. However, your loop still continues and tests for factors using 3,4,5,6,...,9. Why ?

I agree. Here's the better link: Salvin.in

Junilu Lacar wrote:

S Connor wrote:'How many numbers up to 10,000 do you have to test to ensure that you have found all the primes?'

Well it seems to me that you have to test all the numbers up to 9973 to ensure that you have found them all. But how would you translate this into code?

Again, this seems to hint at the Sieve of Eratosthenes...

The question is unclear, though. If you use the Sieve of Eratosthenes then you don't need to test

__any__numbers to see if they are prime. The prime numbers just fall out of the sieve although you never have to test any of them to see if they are prime. When I started typing this I was thinking that you would have to test numbers to see if they are divisible by 2 or 3 or 5 and so on, but you don't even need to do that. You just cross off every second number after 2, every third number after 3, and so on. There's basically no testing of any kind going on.

But I think you should answer the question with √Paul Clapham wrote: . . . If you use the Sieve of Eratosthenes then you don't need to test

anynumbers to see if they are prime. . . . There's basically no testing of any kind going on.

*n*− 1 because 1 doesn't count as a prime number.

Actually, it is not possible to predict how many numbers you would have to go through to find all the prime numbers. In the case of a sieve, you would have to start from 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 52, 59, 61, 67, 71, 73, 79, 83, 89 and 97, which I think is 28, because you start with successive prime numbers. There is no simple formula linking the size of the range and how many prime numbers it contains, though it says in The Curious Incident of the Dog in the Night-Time by Mark Haddon that the number of prime numbers less than

*n*is approximately proportional to log

*n*.

Another thing is that a Sieve will give faster execution than your nested loops; the nested loops will run in

*n*² time; I am not sure but a Sieve might run in

*n*² time too, or it might be possible to run it in

*n*log

*n*time.

Actually Wikipedia says it runs in

*n*(loglog

*n*+ M) time.

Paul Clapham wrote:The question is unclear, though.

In my first reply to OP, I did say that the question was poorly phrased. In the algorithm, you do check if the number has been crossed off so there is still technically a test of some sort. When you find a prime, you go ahead and cross off all its multiples up to N,

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

S Connor wrote:

a)Write a method that determines whether a number is prime. (I can do this part.)

b)Use this method in an application that determines and displays all the prime numbers less than 10,000. How many numbers up to 10,000 do you have to test to ensure that you have found all the primes?

Here's why I think this is poorly worded. Part (a) sets up the whole "testing for prime" context. Part (b) reinforces that context by making the student use the result of (a) to display

*all primes*less than N. The question of "How many ... to test to

*ensure*that you have

*found*all the primes" is an adjunct of part (b), not a separate part (c). Therefore, the implied context of the question is part (b) and the student naturally assumes that counting the numbers being "tested" is part of the algorithm for

*displaying*the prime numbers less than N.

If you're going to

*display*all the prime numbers less than N, then naturally, you're going to have to check

*all*the numbers less than N. That's not really the context of the question though. If anything, part (a) is the proper context for the question because if you use the Sieve algorithm, you really only need to "check" for crossed off numbers up to sqrt(N).

__Anything greater than sqrt(N) is guaranteed to be either a multiple of a prime that is less than sqrt(N) or a prime that is greater than sqrt(N) but less than N__. I guess the real challenge is to give some kind of proof for that assertion so you can support your answer and show that your solution for part (a) is correct.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

A bit set is simply a different sort of class; you only need to know what its methods are:-I see you can get an IntStream out of a BitSet, but what you need to do is work out a way of getting a couple of loops running to create a Sieve. You can probably find the pseudocode easily by searching for Sieve of Eratosthenes.

@OP: why don't you get some clarification from your instructor? I would ask: does this question hint at the Sieve of Eratosthenes as the algorithm to use?

Also, see my earlier comment re the issues with how the assignment is worded and maybe ask some question related to that. Like, What exactly do you mean by "check" in "how many numbers do you have to check to ensure..."? Because if you were to print out the primes less than 10000, the most basic form of the code should look something like this:

Obviously, you're checking

*all*numbers for primality here and this is really where your confusion lies. I've already explained how the poor phrasing of the problem leads to this confusion.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

S Connor wrote:

If arrays are not an option then you can at least optimize your code somewhat.

`a<n`, seeing as how the biggest factor that you could possible have is the square root of 'n' then 'n' should be replaced by a pre-calculated square root:

`int sqrt = (int)Math.sqrt( n );`

`for( int a=3 ; a <= sqrt ; a+=2 )`// edited

Thus halving the number of tests you have to make inside the loop.

If you shouldn't use

`Math.sqrt()`then here's two other approaches that would reduce the number of iterations that you are doing now but they are not ideal compared to sqrt. I'm not sure which would be better.

`for( int a=3 ; a * a <= n ; a+=2 )`

OR

`int half = n / 2;`

for( int a=3 ; a <= half ; a+=2 )

for( int a=3 ; a <= half ; a+=2 )

The most difficult part of wild life photography is getting them to sign the model release.

assuming this is a very, very beginning exercise, let us not say this is a really poorly defined problem, but rather an exorcise that can be later be used to optimize - i.e.: when arrays or data structures are added.

First, let us talk about prime numbers: after you start with 2 you don't need to check any of the other even numbers. so we generate 2 then we start with 3,5,7,9,...

Second, we know that after 3 all primes candidates will fall into 6n +- 1.

so we check for 2, then 3, then in a loop we check 5 and 7, then we check 11 and 13, .... note not all of these candidates are prime, but if it is prime it will be within the candidates.

Also for n - we only need to check up to square root of 10,000.

-steve

The most difficult part of wild life photography is getting them to sign the model release.

You are correct, but what i was trying to throw out there was once you got to sqrt 10000 you had done all of the checking you need to do globally.

Also, the outer loop only need to to iterate to 6n+1 > 10000.

and like you said, the inner loop (inside the isPrime function) only needs to iterate to sqrt n.

thanks for the clarification.

-steve

Steve Fahlbusch wrote:Carey,

You are correct, but what i was trying to throw out there was once you got to sqrt 10000 you had done all of the checking you need to do globally.

Also, the outer loop only need to to iterate to 6n+1 > 10000.

and like you said, the inner loop (inside the isPrime function) only needs to iterate to sqrt n.

thanks for the clarification.

-steve

I'm not sure what you mean by: 6n+1>10000

The biggest prime less than 10000 is 9973, so the outer loop would have to go up through 9999 inclusive.

The most difficult part of wild life photography is getting them to sign the model release.

the 6n +- 1 up to 6n + 1 > 10000 will cover all possible prime candidates up to 10000.

We increment by six as 2 and 3 while prime, 6 * anything is not prime. given that

6n +2 = not prime

6n +3 = not prime

6n +4 (2*2) = not prime

so only 6n + 1 and 6n + 5 could be prime candidates.

now since we are starting from 1 not 0 we have 6n - 1 and 6n + 1.

so we only have to go up to 6n + 1 > 10000 to check all possible prime candidates.

-steve

9973 is 1663 *6 - 1

-steve

My optimized approach took 55,958 tests (% operator) and your approach was 54,292 which is an improvement of 1,666 less tests being made.

I did google prime algorithms and didn't find the one you describe but I assume it's out there on the internet somewhere.

The most difficult part of wild life photography is getting them to sign the model release.

i assume it is out there, but this is simple math.

i am so glad you learned something new, always a great thing.

again, i am surprised that nothing came up on google, it should have.

but what i did was nothing special. being of a instructional background, i am so glad you learned somthing.

Be well my friend,

-steve

- 1

1. OP is confused

2. The replies here show there are multiple ways to interpret what the appropriate solution should be

If you're going to give beginners something to work on to learn the "basics" I don't think the problem should be as confusing or as ambiguous as the many answers to the OP demonstrate. I don't see anything wrong with applying some critical thinking to the problem and if that includes being reasonably critical of the way the problem is presented in the first place, I think that is perfectly fine and if I were the instructor, I would certainly appreciate feedback that would help me improve the students' learning experience.

*Practice only makes habit, only perfect practice makes perfect.*—every music teacher ever

*Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

you are correct. we can reduce the evaluations as we continue.

Great to hear from you again, it has been awhile.

-steve

It is sorta covered in the JavaRanch Style Guide. |