[C. Sherlock and his girlfriend(https://codeforces.com/gym/437178/problem/C)
Approach
We have a bunch of jewelry pieces with different prices. We want to color them in a way that if the price of any piece is a multiple of a prime number, then it should have a different color than the other pieces whose prices are also multiples of that prime number.
To solve this, we need to first find all the prime numbers up to a certain range (in this case, up to 105) using the Sieve of Eratosthenes method. Then, we can color all the jewelry pieces whose prices are prime numbers with one color, and color the rest of the pieces with a different color. This ensures that if a piece's price is a multiple of a prime number, it will have a different color than the other pieces whose prices are also multiples of that prime number.
Code
def build_sieve(num_jewelries):
sieve = [1 for i in range(num_jewelries)]
sieve[1] = 1
i = 2
while i * i <= num_jewelries:
if sieve[i] == 1:
for j in range(i * i, num_jewelries, i):
sieve[j] = 2
i += 1
return sieve
def main():
num_jewelries = int(input())
sieve = build_sieve(num_jewelries + 2)
if num_jewelries > 2:
print(2)
else:
print(1)
for i in range(2, num_jewelries + 2):
print(sieve[i], end = " ")
main()