find all prime numbers less than 10,000

[Paul Clapham]

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.

[Campbell Ritchie]

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.

I would think more like two weeks. I think you can introduce Streams as soon as you introduce arrays. You say,

This is how you create an array filled with 100 instances of 999:-

int[] numbers = new int[100];
Arrays.fill(numbers, 999);

and this is how you create an array containing 100 “random” ints from 0 to less than 10:-

Random myRandom = new Random();
int[] numbers = myRandom.ints(100L, 0, 10)
                        .toArray();

and this is how you create an array containing the ints 101...200:-

int[] numbers = IntStream.range(101, 201)
                         .toArray();

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.

I can't think of a way to implement the SoE algorithm without some kind of data structure . . .

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.

an array of boolean is the most common data structure used. . . .

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 is
myBitSet.set(99999);
or
booleans[99999] = true;
or
myList.set(99999, Boolean.TRUE);
is simply a bit of different syntax.

[Campbell Ritchie]

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.

[Junilu Lacar]

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

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

[S Connor]

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!

[Junilu Lacar]

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"?

[Junilu Lacar]

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.

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.

[S Connor]

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.

[Junilu Lacar]

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.

[S Connor]

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.

[Junilu Lacar]

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.

[S Connor]

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

[Junilu Lacar]

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:

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.

[Carey Brown]

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

public static boolean isPrime( int n ) {
    // implement something along the lines of your inner loop
    // in your earlier posted  code
}

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

    public void findPrimes(){
    int p = 0;
    for ( int n = 1; n < 10000; n++ )   //n will be tested to see if it is a prime number
    {
        if( isPrime(n) )
        {
            System.out.println( n + "  " + (++p)  );
        }
    }
}

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.

[Junilu Lacar]

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"?

[Carey Brown]

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.

[Junilu Lacar]

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

[Junilu Lacar]

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

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

[Campbell Ritchie]

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.

[Junilu Lacar]

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

[Junilu Lacar]

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.

[Carey Brown]

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

	private static boolean isPrime( int n )
	{
		// 2 is a special case
		if( n < 2 )
			return false;
		if( n == 2 )
			return true;
		if( n % 2 == 0 )
			return false;
		
		int sqrt = (int)Math.sqrt( n );
		for( int a=3 ; a <= sqrt ; a+=2 ) // only odd numbers
		{
			if( n % a == 0 )
				return false;
		}
		return true;
	}