On this page
Finding the number of integers in a range that share no factors with a given set of numbers is a classic problem in combinatorics and number theory. It often appears in competitive exams like the JEE. To solve it without manually listing hundreds of numbers, you need a systematic way to count overlapping multiples.
How many numbers up to 1000 are not divisible by 2, 3, or 5?
There are exactly 266 natural numbers up to 1000 that are not divisible by 2, 3, or 5 source.
To find this, we first count how many numbers *are* divisible by at least one of these factors. Then, we subtract that count from the total number of integers (1000). The process requires two mathematical tools: floor division and the principle of inclusion-exclusion.
If you are working through discrete mathematics for an exam, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
How do you count multiples using floor division?
To find the number of multiples of a single integer k within a range up to N, you divide the maximum number by k and round down to the nearest whole number. This is called floor division, written as ⌊N/k⌋.
For N = 1000:
Multiples of 2: ⌊1000/2⌋ = 500
Multiples of 3: ⌊1000/3⌋ = 333
Multiples of 5: ⌊1000/5⌋ = 200
If we simply added these together (500 + 333 + 200 = 1033), our result would be larger than the 1000 numbers we started with. This happens because some numbers are multiples of more than one integer. For example, 6 is counted twice (once as a multiple of 2, and once as a multiple of 3).
What is the principle of inclusion-exclusion?
The principle of inclusion-exclusion is a counting technique that corrects for overlapping sets source. When you have three sets (A, B, and C), the formula for the size of their union is:
|A ∪ B ∪ C| = |A| + |B| + |C| - (|A ∩ B| + |A ∩ C| + |B ∩ C|) + |A ∩ B ∩ C|
Here is how to apply it to our divisibility problem:
1. Include the single multiples: Start with the individual multiples we calculated: 500 + 333 + 200 = 1033.
2. Exclude the pairwise overlaps: Next, we subtract the numbers that are divisible by pairs of our factors. The overlap between multiples of 2 and 3 are the multiples of their lowest common multiple, 6.
Multiples of 6 (2 and 3): ⌊1000/6⌋ = 166
Multiples of 10 (2 and 5): ⌊1000/10⌋ = 100
Multiples of 15 (3 and 5): ⌊1000/15⌋ = 66
Subtract these overlaps: 1033 - (166 + 100 + 66) = 1033 - 332 = 701.
3. Include the triple overlap: By subtracting the pairwise overlaps, we subtracted the numbers divisible by all three factors (multiples of 2 × 3 × 5 = 30) three times. Since we also added them three times initially, they are currently not counted at all. We must add them back once.
Multiples of 30 (2, 3, and 5): ⌊1000/30⌋ = 33
Add this back: 701 + 33 = 734.
So, there are 734 numbers up to 1000 that are divisible by 2, 3, or 5. To find the numbers that are *not* divisible by any of them, we subtract this from 1000:
1000 - 734 = 266.
Is there a faster way to count coprime numbers?
Yes. You can use the repeating pattern of divisibility. The pattern for factors 2, 3, and 5 repeats every 30 numbers (their lowest common multiple).
In the first 30 numbers (1 to 30), the numbers not divisible by 2, 3, or 5 are: 1, 7, 11, 13, 17, 19, 23, and 29. That is exactly 8 numbers. This count is known mathematically through Euler's totient function.
To find the count up to 1000, we divide 1000 by 30 to see how many full blocks of 30 fit into our range: ⌊1000/30⌋ = 33 blocks.
Since each block contains 8 numbers, 33 blocks contain 33 × 8 = 264 numbers.
Finally, we look at the remainder. After 33 × 30 = 990, there are 10 numbers left (991 to 1000). These correspond to the first 10 numbers of the repeating pattern (1 to 10). In the set {1, 2, 3, ..., 10}, only 1 and 7 are not divisible by 2, 3, or 5. That adds 2 more numbers.
264 + 2 = 266.
Both methods arrive at the same answer, but the pattern method is often much faster during a timed test. If you are preparing for exams, exploring multiple ways to solve combinatorics problems in the Fermi Concept Library can help you build this kind of mathematical intuition.
Similar methods are used in other combinatorial puzzles, such as how to count letters in the wrong envelopes, or when you learn how to find the remainder of large powers: JEE methods.
