Consider the first 100 natural numbers. How many of them are not divisible by any one of 2, 3, 5, 7 and 9?
To efficiently test if a number is prime, you only need to check for divisibility by prime numbers less than or equal to its square root. This is because if a number has a factor greater than its square root, it must also have a factor less than its square root. Now, √100 = 10 So, if a number within 1-100 is not divisible by prime numbers in 1-10 range, it would not be divisible by any number more than 10 either. That is, if a number within 1-100 is not divisible by any one of 2, 3, 5, 7, it must be a prime number. So, the question basically requires us to find the number of prime numbers within 1-100 range. We know that, there are 25 prime numbers within 1-100. We need to exclude 2, 3, 5, 7, as these are obviously divisible by themselves. Also, we need to consider the natural number 1, which is not divisible by any one of 2, 3, 5, 7, 9. So required answer = 25 – 4 + 1 = 21 + 1 = 22