Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

Prime-looking numbers

Task number: 3488

We will say that a number is prime-looking if is composite but is not divisible by 2, 3 or 5. The three smallest prime-looking numbers are 49, 77 and 91.

We know that there are 168 primes smaller than 1000. How many prime-looking numbers are there smaller than 1000?

  • Solution

    There are 499 numbers smaller than 1000 that are divisible by two.

    Further 333 divisible by three, 199 divisible by 5, 166 divisible by 6=2⋅3, 99 divsible by 10=2⋅5, 66 divisible by 15=3⋅5 and finally 33 divisible by 30=2⋅3⋅5.

    So using the inclusion-exclusion principle we have 499+333+199−166−99−66+33=733 numbers that cannot be prime-looking, because these numbers are divisble by 2, 3 or 5 – including these prime numbers themselves.

    So we are left with 999−733=266 numbers. But they are not all prime-looking, because some of them are actually prime! According to the assignment there are 168 prime numbers less than 1000, of which we must omit 2,3,5, which we already subtracted earlier. However we must still subtract 1, because it is neither prime nor composite. So we obtain 266−166=100 in all.

  • Answer

    There are 100 prime-looking numbers less than 1000.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email