22 (сложная) Макар выписал несколько трёхзначных чисел. Оказалось, что все числа составлены, но при этом любая пара выписанных чисел состоит из взаимно простых чисел (не имеют общих делителей, кроме 1). Какое наибольшее количество чисел мог выписать Макар?

Рассмотрим трёхзначные числа, кратные 2, 3, 5 и 7. Если два числа имеют общий простой делитель, они не могут одновременно входить в набор.

В качестве примера возьмём числа:

\(101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997\).\)

Все эти числа простые, поэтому любая пара взаимно проста. Количество трёхзначных простых чисел равно \(143\).

Больше получить нельзя: среди составных трёхзначных чисел неизбежно возникают общие простые делители, тогда как простые числа уже дают максимально возможный набор попарно взаимно простых чисел.

Ответ: 143.