Finding the prime numbers between any two given numbers by MR. VEERARAGAVAN EX. RBI OFFICER

Finding the prime numbers between any two given numbers

Sometimes we get questions in entrance examinations to find the number of prime numbers between any two given numbers.

We can use the property of prime numbers to solve this type of question.

We know any prime number greater  than 6 can be expressed as a multiple of 6 +1/-1. For example

19  =  3 × 6 +1

29 =  5 × 6 – 1

But,  the converse need not be true. That is a multiple of 6 +/- 1 can be a composite number.

E.g.    54 +1  and 66 -1 are  composite numbers.

So we can use this property to only to say that a number is not a prime number if it is not a multiple of 6+/- 1. In other words a number cannot be a prime no if it does not satisfy this condition. So we can find all the prime numbers from the numbers which are multiples of 6+/- 1.

Now let us find the prime numbers between 150 and 200. That is prime numbers greater than 150 and less than 200.

The multiples of 6    are   156, 162, 168, 174,  180, 186, 192, and 198

The numbers we get by adding 1 are 157, 163, 169, 175, 181, 187, 193  and 199

The numbers we get by deducting 1 are  155, 161, 167, 173, 179, 185, 191, and 197

Now the problem  is reduced to checking these 16 numbers for prime instead of the 49 numbers from 151 to 199

How to check whether a number is prime or not?

A number is called a prime if it is divisible by only 1 and the number itself. For example 37 can be divided by only 1 and 37 and not by any other number.

(Divisibility means that the number is a multiple of the divisor. That is dividend is the multiplying factor and remainder is zero.)

We can use the following 1 osculator method to check whether a no is prime or not.

Suppose we have to check a no for divisibility by 7.

We take the lowest multiple of 7 which is nearest to a multiple of 10 differing from the multiple of 10 by +1 or -1.

Here, 3 × 7  =  21 (10 × 2  +1)   We get what is called a negative osculator ` -2 ’ (The multiplicand 2 is the osculator  and the sign is negative if the multiplicand of prime factor is above the multiple of 10 and the sign is positive if the multiple of the prime factor is below the multiple of 10. This is how we get the negative osculator -2 for 7)

Next to check the divisibility by 7.

Example: To find divisibility by 7 for the number 273

Multiply the last digit by -2 and

deduct from the number formed by the remaining digits.  27 – 6  = 21 which is multiple of 7

So 273 is divisible by 7

For bigger numbers we repeat the last digit step till we get a 2 digit no.

Example :Check 2569  and 245819 for divisibility by 7.

2569                                                                                                  245819

→ 256 – 2 × 9  = 238                                                                   → 24581 – 18 =  24563

→ 23   — 2 × 8  = 7                                                                        → 2456   –   6 =  2450

So 273 is divisible by 7                                                                 → 245     –   0 =  245

→ 24      – 10 = 14

The  1 osculators for 3, 7, 11, 13, 17, 19, 23, and 29  are  respectively +1, -2, -1, +4, -5, +2, +7, +3.

Even for large numbers normally divisibility by factors upto 13 can be easily checked by direct division.

In entrance examinations divisibility by 17, 19, 23, 29 etc can be done by 1 osculator method. One need not memorize multiplication tables for higher numbers.

We can find osculator for any prime number by the above method.

Let us try a bigger prime factor 37. The osculator is –  11 (Check yourself)

Check the no  87209  for divisibility by 37

87209 → 8720 -99 = 8621 → 862 – 11 = 851 → 85 – 11 =  74 is  a multiple of 37

Let us now find prime numbers between 150 and 200

The highest no is 199 and nearest number greater than the square root of 199 is 15.

So we have to check the 16 numbers for prime factors below 15. They are 2,3,5, 7,11 and 13.

We don’t have to check for 2 and 3 because they are eliminated by selecting multiples of 6 +/- 1.

Checking for 5 we eliminate 155, 175 and 185

Now we check for multiple for 7

Multiples of 7 can end in last digit of 7,4,1,8,5,2,9,6, 3, 0

S o we have to check 157, 161, 163, 167,  169, 173, 179, 181, 187, 191, 193,197, 199

To check for divisibility by 7, multiply last digit by 2 and subtract the product from the remaining 2 digit number. The resulting no should be 0 or divisible by 7. Then the original no is divisible by 7.

For instance 157 is tested like this

15 – 7×2 = 15 -14 =1. Therefore 157 is not divisible by 7.

This test we can carry out mentally and find 161 is a multiple of 7

For checking for 11 we deduct the last digit from the number formed by the first two digits. If the difference is 0 or a multiple of 11 then the original number is divisible by 11.

This test also we can carry out mentally.

We find 187 is divisible by 11.

Checking for divisibility by 13.

We multiply the last digit by 4 and add it to the number formed by the first 2 digits. If the result is a multiple of 13 the original number is divisible by 13.

Carrying out this test mentally we find 187 is the only number divisible by 13

Thus out of  16 numbers  which are multiples of 6 increased or decreased by 1,five numbers namely,  169, 175, 155, 185,  and 187 are composite numbers.

Thus we have 11 prime numbers between 150 and 200.

Another example:

Let us find the prime numbers from 1 to 100

Multiples of 6 are  6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96

There are 32 possible nos  5, 7, 11, 13, 17, 19, 23, 25,  29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97

We know 2,3, and 5 are prime numbers.

Similarly 11, 13,  17, 19 are prime numbers.

There are 26 numbers starting from 23

25, 35, 55, 65, 85,  are multiples of 5

Applying test for 7 the first multiple of 7 is 49. Then 77 and 91 are also multiples of 7.

Testing for 11 we don’t get any no. We stop here

So we are left with 25 prime numbers from 1 to 100 are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,

53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Find the prime numbers between 900 and  1000.

Multiples of 6 are  906,912, 918, 924, 930, 936, 942, 948, 954, 960, 966, 972, 978, 984, 990, 996

The numbers on both sides of multiples of 6 are

905, 907, 911, 913, 917,919, 923, 925, 929, 931, 935, 937, 941, 943, 953, 955, 959, 961, 965, 967, 971, 973, 977, 979, 983, 985, 989, 991, 995  and  997.

Out of these 30 numbers, sixteen,  namely,  905, 913,917, 923, 925, 931, 935,943, 955,959, 961,965,973,  979, 985,  and  995 are composite numbers

Thus there are 14  prime numbers between 900 and 1000.

They are 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.