Problem in Short
Print the first N prime numbers where N is accepted from the user.
Hint 1
Click to view
First let us figure out how to write code to check whether a number is prime or not.
Hint 2
Click to view
What is a prime number? How many factors a prime number has? What are those?
Click to view
A prime number is one which has only two factors 1 and itself.
Hint 3
Click to view
So how can we check whether a number P is prime or not? A prime number will never have a factor in what range
of numbers?
Click to view
Can we not say a prime number is one which has no factors between 2 and P-1?
Hint 4:
Click to view
Then how do we write the code to do it? Loops?
Click to view
Run a loop from 2 to P-1 each time incrementing the counter by 1.
Check if the number is divisible by the counter or not. If divisible we know the number is not
a prime and we can break out from the loop.
Hint 5:
Click to view
But there is a small problem. How do we know when we come outside the loop that whether we encountered a factor of P between 2 and P-1 or not. After all whether we encounter a factor or not we will come outside
the loop. We must be in a position to understand whether any factor was encountered or not.
Click to view
Think that you have a bag and a ball outside it. If we encounter a factor let’s put this ball in the bag.
In the end if we find the ball inside the bag what does it mean? Can you put this in code? Can the ball be
some variable?
Click to view
Here comes the need of a variable called flag. We start by saying flag=0 which means that no factor is encountered. The moment we encounter a factor we make flag=1. Later outside the loop if this value of flag is 0 we know that no factor has been encountered and the number is a prime number.
Hint 6:
Click to view
Now that we know how to check whether a number is prime or not let’s turn our attention to printing the first N prime numbers.
Hint 7:
Click to view
How long do we continue printing prime numbers?
Click to view
As long as the number of primes printed so far is less than N(the moment we have N primes we stop), right? So we need some variable to keep track of how many primes are printed so far(say cnt)? Initially how many primes have we printed. 0. So initialize cnt to 0.
Hint 8:
Click to view
Okay, now we have a way to keep track of how many primes are printed and we know when to stop printing primes? But what numbers to check whether it is a prime or not. May be keep a different variable.
Hint 9:
Click to view
Lets have another variable(say i).Every time we check if this variable is prime or not. What number do we start checking with?
Click to view
Let’s initialize i with 2 because we want to start checking from 2.
Hint 10:
Click to view
Every time we find i is a prime number what do we do. What are we asked to do with the prime numbers?
Click to view
Lets print the number i and since we got a prime number lets increment cnt(count of
prime numbers printed) by 1. Then we have to move to the next number so increment i by 1.
Hint 11:
Click to view
Every time i is not a prime what do we do. Lets go to the next number to check whether that number is a prime or not, right?
Click to view
So increment i by 1. That’s it!
Hint 12:
Click to view
Now you must have got a time limit exceeded when you submitted that code. Refer to hint 3. What did we say
about prime numbers? A prime number P certainly has no factors between 2 and P-1 because the only two factors
it has are 1 and itself. Now can you modify the above range. Can you check for a smaller range than
2 to P-1. Write down the factors of a number. Do you observe any trend? For every number P what is the maximum number less than which all the factors of P are? Of course it is less than P-1. Can you do better?
Click to view
If you have observed that it is less than equal to (P/2) you are absolutely correct. But you can do a better.
Hint 13:
Click to view
You must have noticed that factors always occur in pairs. Consider the pair in which (P/2) is the factor. What is the other
factor?
Click to view
Just divide P by (P/2). And what are you left with? 2. Right?
Hint 14:
Click to view
So instead of checking the divisibility of P with (P/2) can we not check the divisibility of P with 2.
If P is divisible by (P/2) doesn’t it means that P is also divisible by 2. So can we avoid going up till (P/2)?
Hint 15:
Click to view
Observing a bit carefully you will notice that after a particular number the factors(in pairs) start reappearing.
Can you see after which number does this happens?
Click to view
Lets take an example. Write down the factors of 12. It is:
2*6
3*4
4*3
6*2
You can see that the first pair and the last pair are essentially the same. Only their orders are different.
Note the factor after which the pairs repeat. The pairs start repeating after 3*4 , right? So isn’t checking all the
numbers from 2 to 3 enough because after this there are repetitions.
Hint 16:
Click to view
Work out for 16. Can you generalize for any P what is the maximum value I must check till to get any factor?
Click to view
2*8
4*4
8*2
Isn’t after the second pair the pairs start repeating? So isn’t it enough to check from 2 to 4. We will get all our
factors in this range because after this the same pairs repeat only the order of factors change. 4 is 16's what?
What mathematical operation do you do on 16 to get 4?
Hint 17:
Click to view
Square Root? Well may be, may be not. Try with a few more examples.
Click to view
It turns out that it is indeed square root of P. All distinct factors of a number are between 2 and square root of that number. Only the previous pairs of factors repeat with the order of factors in the pairs changed.
Hint 18:
Click to view
We guessed and observed that it is square root of a number P. Can we prove it? I will give you an idea of how we prove something like this using a proof technique called Mathematical Contradiction. In this technique we take the wrong assumption and prove that indeed the wrong assumption is an incorrect assumption. In this case the wrong assumption is we would encounter a pair of factors in which both the factors in that pair is greater than square root of P. Now I ask you a question. Is this possible? If we multiply two such factors what do we get?
Click to view
If we multiply two factors greater than sqrt(P) we get a number greater than P. So it is indeed incorrect to assume that there will be a pair of factors where both the factors are greater than sqrt(P).
We can at most assume that two factors in a pair are equal to sqrt(P) because sqrt(P)*sqrt(P)=P.