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.
