find all prime numbers less than 10,000

[S Connor]

Hello,

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

[Junilu Lacar]

First, I think the question is poorly phrased and creates the kind of confusion you have. Second, I think the question is hinting at the Sieve of Eratosthenes. Study that algorithm and take particular note of the upper limit of the outermost loop, which is significantly less than N for large values of N.

[Campbell Ritchie]

. . . but I would expect a Sieve of Eratosthenes to be easily extensible to larger values, and it shouln't need even 10″ to find all prime numbers < 100,000,000.

[S Connor]

Is it possible to use the sieve without needing an array?

[Paul Clapham]

Of course. Why do you think an array would be a requirement?

[S Connor]

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

[Paul Clapham]

Yeah, that's true. But you could "record" them by writing them to the console, or adding them to some kind of List, for example. You could use an array but then you'd have to make sure it was big enough to hold all the primes you found. Which is also possible. I'm just saying that you don't have to use an array.

[salvin francis]

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 ?

[salvin francis]

Hint, there is a trick to know when to stop as mentioned in the wiki page. In their example, for a range of 30, they stopped at 7. This is because 7x7=49 which is greater than 30. I guess this will help in answering the second part of the question.

[Piet Souris]

If one had to investigate whether some number is a prime or not, would one use a Sieve to check that one number? Maybe, maybe not. Assignment part 1 is about creating a method to determine if some number is a prime.
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?

[salvin francis]

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

[Piet Souris]

Thank you for the cow!

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!

[S Connor]

Thanks for the advice. I am following an exercise book which has not so far mentioned sets or recording to console.  Now that I think about it, an array to store the numbers would be unwieldy at best.  I'm wondering if there is an elegant solution that does not require recording of which numbers are prime?

[Piet Souris]

Well, I used a small elegant version of the Sieve, that uses a simple recursion which could easily also be done with a while or a for loop.

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?

[salvin francis]

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.

[S Connor]

Here is my solution to the first part of the problem.

public class Primes {
    
    public void findPrimes(){
        
    boolean nhasfactor = false;
    int p = 0;
    
    for ( int n = 1; n < 10000; n++ )   //n will be tested to see if it is a prime number
    {
        for ( int a = 2; a < n; a++ )//test whether n is a prime by checking whether it has any factors
        {
            if ( n % a == 0  ) //n has a factor
            {
                nhasfactor = true;
            }
       }
        if ( nhasfactor == false)  //n is a prime number. 
        {
            p++;
                System.out.printf("%d is prime number %d\n", n, p);
        }
        nhasfactor = false;
    
    }
}
}

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?

[Junilu Lacar]

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.

[salvin francis]

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 ?

[Paul Clapham]

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.

[Campbell Ritchie]

Paul Clapham wrote: . . . If you use the Sieve of Eratosthenes then you don't need to test any numbers to see if they are prime. . . . There's basically no testing of any kind going on.

But I think you shou‍ld answer the question with √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 logn.

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

Actually Wikipedia says it runs in n(loglogn + M) time.

[Junilu Lacar]

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, thus eliminating the need to "check" them later. so any number less than sqrt(N) will be "crossed off" and deemed as a non-prime when it is "checked" later on in the loop.

[Junilu Lacar]

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.

[S Connor]

It would seem that I need a way to mark the numbers in the sequence that are not prime. Do you have any suggestions of how I might do this please? I saw that someone mentioned lists abobe,  however this has not been covered in my exercise book so far and nor have atrays nor writing to console as someone earlier suggested.

[Campbell Ritchie]

You can use a List<Boolean> as the basis of a Sieve, or a boolean[] or even a BitSet. You will probably find the array the easiest to use at your stage, but the BitSet will have the least memory consumption.

[S Connor]

Thank you for the suggestion, however at this stage in the exercise book there has not yet been any mention of arrays or bit set.   I'm wondering if there is a solution using the basics?

[Campbell Ritchie]

An array is a “basic” of the language.

A bit set is simply a different sort of class; you only need to know what its methods are:-

import java.util.BitSet;
// ...
BitSet primes = new BitSet(1_000_001);
/* Indices run 0...1,000,000 inclusive */
primes.set(2, 1_000_000); // set everything true except 0, 1=not prime
// ...
primes.clear(99999); // 99999 isn't prime
// ...
for (int i = 0; i < primes.size(); i++)
{
   if (primes.get(i))
   {
      System.out.printf("%d ", i);
   }
}

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.

[Campbell Ritchie]

Only just noticed the BitSet#stream() method. What would happen if we did this sort of thing?

System.out.println(myBitSet.stream()
                           .mapToObj(String::valueOf)
                           .collect(Collectors.joining(", ", "[", "]")));

[Junilu Lacar]

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 can't think of a way to implement the SoE algorithm without some kind of data structure to keep track of which numbers have been marked off as multiples of a lesser prime number. As already mentioned multiple times, an array of boolean is the most common data structure used. There are other algorithms for determining primality of numbers but again, taking everything that was given in the problem statement into consideration, I'm pretty sure that the answers are expected to be based on the SoE algorithm.

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

for (int p = 2; p < 10000; p++) {
    if (isPrime(p)) {
        System.out.println(p);
    }
}

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.

[Carey Brown]

S Connor wrote:

public class Primes {
    
    public void findPrimes(){
        
    boolean nhasfactor = false;
    int p = 0;
    
    for ( int n = 1; n < 10000; n++ )   //n will be tested to see if it is a prime number
    {
        for ( int a = 2; a < n; a++ )//test whether n is a prime by checking whether it has any factors
        {
            if ( n % a == 0  ) //n has a factor
            {
                nhasfactor = true;
            }
       }
        if ( nhasfactor == false)  //n is a prime number. 
        {
            p++;
                System.out.printf("%d is prime number %d\n", n, p);
        }
        nhasfactor = false;
    
    }
}
}

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

In your inner loop you have a test for 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 );

If you treat even numbers as a special case in an if() statement after line 9, that allows you to optimize the inner loop (inside an 'else' block) to
for( int a=3 ; a <= sqrt ; a+=2 ) // edited
Thus halving the number of tests you have to make inside the loop.

And for the inner if() you should break out of the loop once you find that n-has-a-factor is true.

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 )

[Steve Fahlbusch]

Greetings,

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

[Carey Brown]

I initially made the same mistake about square root of 10,000. If the outer loop is incrementing 'n' by one each time, the the limit on the inner loop should be sqrt(n), not sqrt(10000).

[Steve Fahlbusch]

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

[Carey Brown]

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.

[Steve Fahlbusch]

Carey,


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

[Steve Fahlbusch]

Also,

9973 is 1663 *6 - 1

-steve

[Carey Brown]

Interesting. I learned something new.
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.

[Steve Fahlbusch]

Corey,

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

[Paul Clapham]

Testing only numbers of the form 6n+1 and 6n+5 requires testing 1/3 of the numbers. The next step to reduce that is testing numbers of the form 30n+1, 7, 11, 13, 17, 19, 23, and 29. This requires testing only 4/15 of the numbers, which is less than 1/3. You can continue this process...

[Junilu Lacar]

I don't see why there's a need to pussyfoot around the fact that the problem is poorly phrased given that:

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.

[Steve Fahlbusch]

Greetings Paul,


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

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

-steve