Find the sum of all natural numbers less than and coprime to $N=25200$ I have factorized the number $25200=2⋅2⋅2⋅2⋅3⋅3⋅5⋅5⋅7$. I found the sum of all numbers from $1$ to $25199$. I got the number $317507400$. Then, as I understand it, I have to calculate the sums of all numbers that are multiples of $2;3;5;7$ and subtract these sums from the total. But at the same time, one must probably take into account that, for example, in the number $6$ there are already $2$ and $3$, and in the number $15$ there are already numbers $3$ and $5$, and there are many such options and how to take this into account is not very clear. Or is there an easier way to solve it?
 A: Hint: The numbers less than $25200$ and coprime to $25200$ come in pairs of the form $k, 25200 - k$. Then: do you know how many numbers there are coprime to $25200$?
A: Since the number of prime factors of $N$ is small, you can find the desired sum by continually correcting for higher and higher numbers of shared prime factors.
You start by adding all the numbers less than $N$, as shown below. Let $n$ be the number of prime factors shared between $N$ and an arbitrary number less than $N$.
$$\begin{matrix}
n&0&1&2&3&4 \\
{\rm  Times\  counted:}&1&1&1&1&1
\end{matrix}$$
By subtracting numbers for each shared prime factor, we get the following:
$$\begin{matrix}
n&0&1&2&3&4 \\
{\rm  Times\  counted:}&1&0&-1&-2&-3
\end{matrix}$$
As you noted, you seem to be stuck on the negative values for $n\geq2$. We can simply correct for these by adding back values that share a pair of prime factors (ie. $6,10,15$). For each triple, there are 3 unique pairs, and for each quadruple, there are 6 pairs, so we get the following:
$$\begin{matrix}
n&0&1&2&3&4 \\
{\rm  Times\  counted:}&1&0&0&1&3
\end{matrix}$$
Now we can subtract the values that are divisible by a triple of prime factors (ie. $30,42$). There are 4 unique triples in the quadruple, so:
$$\begin{matrix}
n&0&1&2&3&4 \\
{\rm  Times\  counted:}&1&0&0&0&-1
\end{matrix}$$
Finally, we can add back the quadruple shared prime factors (divisible by $210$) to get the following:
$$\begin{matrix}
n&0&1&2&3&4 \\
{\rm  Times\  counted:}&1&0&0&0&0
\end{matrix}$$
And this is your desired result. In general, you can find the sum of the coprime numbers by subtracting for odd numbers of prime factors, and adding back for even numbers of prime factors.
