Following Andy Putman's suggestion that we use the nerve complex, I believe I have found an inductive proof that $H_1(X_n) = 0$ for all $n$. Please point out errors if you see any!

Let $X_n$ denote the nerve complex as described in Andy Putman's answer, though for simplicity's sake we make the vertex set $[n]$. (So $\{1\}$ is always an isolated vertex of $X_n$.) All homologies below are reduced, but I'll write $H_k$ instead of $\tilde H_k$ to be lazy.

We'll need the following fact later on, so I'll state it here, but I'll omit its proof. (It's not too difficult.)

__Proposition.__  We have
$$H_0(X_1) = 0,\qquad H_0(X_2) = {\bf Z},\qquad\hbox{and}\ H_0(X_3)={\bf Z}^2.$$
For $n\ge 4$, the vertex $1$ is isolated in $X_n$, and there is also an isolated vertex in $X_n$ for each prime in the range $(n/2,n]$. The rest of the vertices are in one connected component. In other words, $H_0(X_n) = {\bf Z}^{C(n)+1}$, where $C(n)$ is the number of primes in the range $(n/2,n]$. ▮

We'll also use the Mayer--Vietoris sequence, which for reduced homology states that 

$$\eqalign{
\cdots \to H_s(A)\oplus H_s(B) \to  H_s(X)\to H_{s-1}(A\cap B) \to
H_{s-1}(A)\oplus  H_{s-1}(B)\to\cr
\cdots\to H_0(A\cap B) \to H_0(A)\oplus  H_0(B) \to  H_0(X) \to 0,\cr
}$$

whenever $A$ and $B$ are subsimplicial complexes whose interiors cover $X$, and $A\cap B$ is nonempty.

_Proof that $H_1(X_n)=0$ for $n\ge 1$._ We begin the induction on $n$.
For $n=1$ it is clear that $H_k(X_1)$ is $0$ for all $k$.

Now let $n>1$. If $n$ is prime, then $X_n$ is simply the union of $X_{n-1}$ and a new isolated vertex, so $H_0(X_n) = H_0(X_{n-1}) \oplus {\bf Z}$, but all other homologies remain unchanged, so by the induction hypothesis, $H_k(X_n) = 0$ for all $k>1$.

If $n$ is not prime, we let $A$ be the cone of the vertex $n$ in $X_n$, and let $B = X_{n-1}$, considered as a subset of $X_n$. The relevant section of the Mayer Vietoris sequence is

$$\cdots \to H_1(A)\oplus H_1(B) \to H_1(X_n)
\to H_0(A\cap B) \to H_0(A)\oplus  H_0(B) \to  H_0(X_n) \to 0$$

Note that $A$, being the cone of a vertex, is contractible. Applying the proposition above, we have $H_0(X_n) = C(n)+1$ and $H_0(B) = C(n-1)+1$. By the induction hypothesis, $H_1(B) = 0$. Lastly, note that $A\cap B$ is a subset of the big connected component, unless $n/2$ is prime, in which case it also contains the isolated vertex $n/2$, which is isolated in $B$. Hence
$$ \hbox{rank}(H_0(A\cap B)) = {\bf 1}_{[n/2\text{ is prime}]}.$$

Putting all these facts into the exact sequence above, we have

$$\cdots \to 0 \to H_1(X_n)
\to {\bf Z}^{{\bf 1}_{[n/2\text{ is prime}]}} \to 0 \oplus  {\bf Z}^{C(n-1)+1}\to  {\bf Z}^{C(n)+1} \to 0$$

But since $n$ is composite, we have
$$C(n) = \cases{C(n-1)-1, & if $n/2$ is prime;\cr C(n-1), & otherwise.}$$
Thus we conclude that $H_1(X_n) = 0$. ▮

I feel like this Mayer--Vietoris idea is very close to showing that $H_k(X_n) = 0$ for $k>1$ as well. Since $H_k(A) \oplus H_k(B) = 0$ for all $k>1$, we have
$$H_k(X_n) = H_{k-1}(A \cap B)$$
for $k>1$, but it is not immediate to me that the homologies of the intersection are all trivial.