- 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

posted 1 year ago

I have to say, many of us (unfortunately including me) are just showing off and I don't think we're helping the OP very much. Hopefully the OP can cut through all the smoke and glean something useful from the thread.

Junilu Lacar wrote:the many answers to the OP...

I have to say, many of us (unfortunately including me) are just showing off and I don't think we're helping the OP very much. Hopefully the OP can cut through all the smoke and glean something useful from the thread.

posted 1 year ago

`myBitSet.set(99999);`

or

`booleans[99999] = true;`

or

`myList.set(99999, Boolean.TRUE);`

is simply a bit of different syntax.

I would think more like two weeks. I think you can introduce Streams as soon as you introduce arrays. You say,Junilu Lacar wrote:If OP thinks arrays are too advanced right now, I'd bet dollars to donuts that streams are about two semesters worth of coursework above his learning level at this point.

You then have to explain a bit about how the Streams work, and then show how much nicer the code is than what you get with a for loop. I think there is going to more confusion about why my random array doesn't contain 10. Streams are objects, so it is a more object‑oriented solution than a loop.This is how you create an array filled with 100 instances of 999:-and this is how you create an array containing 100 “random”

ints from 0 to less than 10:-and this is how you create an array containing theints 101...200:-

Nor can I. The data structure, even if it is only numbers written on a sheet of paper, as shown in the Wikipedia page, is an essential part of a Sieve algorithm. Wikipedia also suggests there are other kinds of sieve.I can't think of a way to implement the SoE algorithm without some kind of data structure . . .

And you can use it in a similar fashion to what I showed with the bit set. In fact any data structure can be used in a similar fashion; it is the same concept and whether it isan array of boolean is the most common data structure used. . . .

or

or

is simply a bit of different syntax.

Campbell Ritchie

Marshal

Posts: 61691

193

posted 1 year ago

But if OP really hasn't been introduced to arrays, is this assignment over their head? OP is now stuck with the inelegant solution with a plain simple loop which Junilu showed.

posted 1 year ago

That's really the main concern in these situations, where assignments given seem to require more knowledge than what has already been covered in class.

The difference between two weeks vs two~~years~~ semesters in our estimations is basically because of different expectations. Your two weeks is based on an expectation that instructors will teach objects very early on. The reality of academic instruction doesn't seem to meet that expectation though. Our experience with many posters here and my own experience with students in the real world shows that proper object oriented programming techniques often aren't taught when discussing "the basics." Often, it's not even until after the second programming course. My son took two Java programming classes and it wasn't until the last part of the second course when they were introduced to some object oriented programming techniques. Up until then, they were writing mostly static methods and I would often see most of their code examples have huge main() methods.

Campbell Ritchie wrote:But if OP really hasn't been introduced to arrays, is this assignment over their head? OP is now stuck with the inelegant solution with a plain simple loop which Junilu showed.

That's really the main concern in these situations, where assignments given seem to require more knowledge than what has already been covered in class.

The difference between two weeks vs two

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

Campbell Ritchie

Marshal

Posts: 61691

193

posted 1 year ago

Yes, I keep forgetting how badly some things are done in some places

posted 1 year ago

If I have understood this correctly, the question is not asking 'how many valyes of n up to 10,000 do you have to test' since you have to test pretty much all values of n.

Instead it is asking, when testing values of n, what size number to you need to test up to to know you have found all the factors and thus whether n is a prime number. Is that correct?

By the way I am not a college student, just have taken up coding as a hobby. I'm really happy to have your help with this!

Instead it is asking, when testing values of n, what size number to you need to test up to to know you have found all the factors and thus whether n is a prime number. Is that correct?

By the way I am not a college student, just have taken up coding as a hobby. I'm really happy to have your help with this!

posted 1 year ago

No, I don't think that's a good way of interpreting it, or at least stating what your interpretation is. That statement it isn't very coherent. In particular, "testing values of n" doesn't make sense. If you have N=10000, what exactly are these "values of n"?

S Connor wrote:

Instead it is asking, when testing values of n, what size number to you need to test up to to know you have found all the factors and thus whether n is a prime number. Is that correct?

No, I don't think that's a good way of interpreting it, or at least stating what your interpretation is. That statement it isn't very coherent. In particular, "testing values of n" doesn't make sense. If you have N=10000, what exactly are these "values of 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]

posted 1 year ago

Here's why I keep going back to the Sieve of Eratosthenes. If you use that algorithm to find all the prime numbers up to 10000, your main loop only needs to go to sqrt(10000) or 100. Why only 100? Because if you follow the algorithm, you're checking whether the numbers from 2 to 100 have been processed such that all their multiples up to 10000 have been "crossed off" as being non-prime. The implication is that once you have crossed off all the multiples for the numbers less than 100, all the remaining numbers less than 10000 are *guaranteed* to be prime. In other words, there is no need to proceed past 100 and cross off the multiples of the next prime (101) because that's already guaranteed to have happened.

This is why I said that the way the question was phrased in the first place was not very clear.

It would have been much clearer if there was a specific algorithm mentioned because the algorithm will determine the answer. In the case of the SoE, you only have to "check" or cross off the multiples of all primes up to sqrt(N) to guarantee that you have found all the prime numbers less than N.

This is why I said that the way the question was phrased in the first place was not very clear.

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

It would have been much clearer if there was a specific algorithm mentioned because the algorithm will determine the answer. In the case of the SoE, you only have to "check" or cross off the multiples of all primes up to sqrt(N) to guarantee that you have found all the prime numbers less than 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

Ranch Hand

Posts: 30

posted 1 year ago

Thanks for your response.

What I am still not clear on is how I can 'cross off' numbers. I don't have any way to record which values of n are prime or not.

What I am still not clear on is how I can 'cross off' numbers. I don't have any way to record which values of n are prime or not.

posted 1 year ago

You're making this way too difficult for yourself.

If you're going to use the Sieve algorithm, you NEED some kind of data structure to keep track of the numbers that are prime vs. non-prime. This is where the question of "How many do you need to check to ensure you've found all the prime numbers?" makes sense. In any other context, this question makes no sense.

Like if you're just going to do factorization to determine primality, without keeping track of the results of any of your previous checks, then the question makes no sense. You have to check ALL numbers if you're going to use this approach to determine primality.

If you're going to use the Sieve algorithm, you NEED some kind of data structure to keep track of the numbers that are prime vs. non-prime. This is where the question of "How many do you need to check to ensure you've found all the prime numbers?" makes sense. In any other context, this question makes no sense.

Like if you're just going to do factorization to determine primality, without keeping track of the results of any of your previous checks, then the question makes no sense. You have to check ALL numbers if you're going to use this approach to determine primality.

*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

Ranch Hand

Posts: 30

posted 1 year ago

That's what I thought. However the programming book I am studying from which the question originates has not yet covered data structures of any kind. I thought there might be a clever way to do this that I had missed.

posted 1 year ago

I don't know what book you're using so I can't really say whether it's something the author overlooked when he/she was arranging the exercises or if there was an assumption that the reader already had some basic knowledge about arrays. If you give more details about the book, maybe we can check it out for ourselves and give you an opinion.

*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

Ranch Hand

Posts: 30

posted 1 year ago

The book is called Java how to program seventh edition by Dietel and Dietel chapter 6 ex 25

posted 1 year ago

Looking at the seventh edition of that book, arrays are introduced in the next chapter, Chapter 7. There is a third part of that exercise that you didn't include in your original post:

This part supports my assertion that the authors are alluding to the Sieve of Eratosthenes algorithm. I don't know why they put this exercise in the chapter preceding the one about arrays though nor do I know of any way to implement the SoE without the aid of a data structure.

Deitel wrote:

(Chapter 6, exercise 25)

...

3. Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only go as high as the square root of n. Why? Rewrite the program, and run it both ways.

This part supports my assertion that the authors are alluding to the Sieve of Eratosthenes algorithm. I don't know why they put this exercise in the chapter preceding the one about arrays though nor do I know of any way to implement the SoE without the aid of a data structure.

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

posted 1 year ago

I haven't seen any code provided by you that does (a). I would expect something like

Your outer loop then looks like (note: any number < 2 cannot be prime):

isPrime() has opportunities for optimization (refer to my earlier post) but the key is to get it to work correctly first. Be aware that '2' is a special case.

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 haven't seen any code provided by you that does (a). I would expect something like

Your outer loop then looks like (note: any number < 2 cannot be prime):

isPrime() has opportunities for optimization (refer to my earlier post) but the key is to get it to work correctly first. Be aware that '2' is a special case.

posted 1 year ago

If something like that is the implementation that the authors expected, how does the third part of the exercise, which I quote previously, make sense? Why do they specifically say in that part that "you need only go as high as the square root of 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]

posted 1 year ago

One of the optimizations that can be made to the innards of isPrime() is have a loop whose limit is the sqrt(n). No sieve involved.

posted 1 year ago

Ok, this is correct even for the factorization approach. I still think that it doesn't make sense in the context of the part that asks "How many numbers up to 10,000 do you have to test to ensure that you have found all the primes?" though. I think the exercise in its entirety is poorly structured and misleading.

It would have made more sense if the question given was "How many numbers do you have to check to ensure that N is a prime number?" This question would make more sense when taken with the statement they make in part 3:*Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only go as high as the square root of n. Why?*.

Carey Brown wrote:One of the optimizations that can be made to the innards of isPrime() is have a loop whose limit is the sqrt(n). No sieve involved.

Ok, this is correct even for the factorization approach. I still think that it doesn't make sense in the context of the part that asks "How many numbers up to 10,000 do you have to test to ensure that you have found all the primes?" though. I think the exercise in its entirety is poorly structured and misleading.

It would have made more sense if the question given was "How many numbers do you have to check to ensure that N is a prime number?" This question would make more sense when taken with the statement they make in part 3:

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

posted 1 year ago

Here's the entire exercise as it appears in the seventh edition:

Here's how I think it could be improved so that it isn't as misleading and~~it can be solved without using~~ *leads* you to the solution that doesn't use arrays.

6.25 An integer is said to be prime if it is divisible by only 1 and itself. For example, 2, 3, 5 and 7 are prime, but 4, 6, 8 and 9 are not.

1. Write a method that determines whether a number N is prime by checking if it is only divisible by 1 and itself.

2. Use this method in an application that determines and displays all prime numbers less than 10,000.

3. How many numbers do you need to check to ensure that N is prime? Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only to go as high as the square root of N. Why? Rewrite your application and see if its output differs from what you got before.

6.25 An integer is said to be prime if it is divisible by only 1 and itself. For example, 2, 3, 5 and 7 are prime, but 4, 6, 8 and 9 are not.

1. Write a method that determines whether a number is prime.

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

3. Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only go as high as the square root of n. Why? Rewrite the program, and run it both ways.

Here's how I think it could be improved so that it isn't as misleading and

6.25 An integer is said to be prime if it is divisible by only 1 and itself. For example, 2, 3, 5 and 7 are prime, but 4, 6, 8 and 9 are not.

1. Write a method that determines whether a number N is prime by checking if it is only divisible by 1 and itself.

2. Use this method in an application that determines and displays all prime numbers less than 10,000.

3. How many numbers do you need to check to ensure that N is prime? Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only to go as high as the square root of N. Why? Rewrite your application and see if its output differs from what you got before.

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

Campbell Ritchie

Marshal

Posts: 61691

193

posted 1 year ago

It is slightly different in the 6th edition which I have (page 282). It starts the same and finishes

...Rewrite the program and run it both ways. Estimate the performance improvement.

posted 1 year ago

I think it's good they took out the part about performance improvement starting from the 7th edition. I don't think that kind of focus is appropriate for beginners who are still learning the basics of the language.

The misleading parts that I've pointed out in this thread, however, remain even up to the 10th edition (Early Objects). The only difference between the 7th and the 10th editions is an additional note in the latter: "...but 4, 6, 8 and 9 are not.__The number 1, by definition, is not prime__."

The misleading parts that I've pointed out in this thread, however, remain even up to the 10th edition (Early Objects). The only difference between the 7th and the 10th editions is an additional note in the latter: "...but 4, 6, 8 and 9 are not.

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

posted 1 year ago

Since OP said he could do the `isPrime()` part and even though he hasn't shared his work, he also said he's not a student so I don't think there's any harm in sharing a solution.

Here's a basic implementation that checks for factors: https://repl.it/MVM4/7

Here are a couple that use the Sieve of Eratosthenes algorithm:

https://repl.it/MUpa/15 - uses a boolean[] as a sieve

https://repl.it/MUpa/12 - uses a java.util.BitSet as a sieve

I found that it helps to test with 28 as well. This can reveal a subtle bug. There are 1229 primes that are less than 10,000 and 9 primes that are less than 28. The subtle bug made my code report 10 primes less than 28.

Here's a basic implementation that checks for factors: https://repl.it/MVM4/7

Here are a couple that use the Sieve of Eratosthenes algorithm:

https://repl.it/MUpa/15 - uses a boolean[] as a sieve

https://repl.it/MUpa/12 - uses a java.util.BitSet as a sieve

I found that it helps to test with 28 as well. This can reveal a subtle bug. There are 1229 primes that are less than 10,000 and 9 primes that are less than 28. The subtle bug made my code report 10 primes less than 28.

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

posted 1 year ago

- 1

A somewhat optimized version of isPrime(n) without using sieve.

It is sorta covered in the JavaRanch Style Guide. |

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!