How prove there exist prime numbers $P_{1},P_{2},\cdots,P_{n}$ such $P_{k}\mid c+k$ Question:

Let $c,n\in\mathbb{N}$, such that, $c&gt;n^{n-1}$.
Show that: there exist distinct prime numbers $P_{1},P_{2},\dots,P_{n}$ such that:
$$P_{k}\mid c+k,k=1,2,3,\dots,n$$

My idea: if $c+k$ have greater than $n$ factor,this problem It is clear .
But other case,I can't
As others pointed out, what I wrote earlier did not work, and I spent several hours failing to fix it. But a correct solution turns out to be already published.

@JeppeStigNielsen [Comment under question] pointed out that this is related to Grimm's Conjecture. Grimm's Conjecture is similar but with the requirement that $c&gt;n^{n-1}$ replaced by the requirement that the $n$ numbers $c+1,\dots,c+n$ be composite.

But in his original paper (American Mathematical Monthly 76 (1969) p1126), he proves the result above. The proof is quite short:

Consider the prime factoring of $c+1,\dots,c+n$. If $c+k$ is divisible by more than $n-1$ distinct primes, then no matter what primes are factored from the other $n-1$ numbers $c+j$ there would be a prime to factor from $c+k$. Hence we assume $c+k$ has fewer than $n$ distinct prime factors $p_{1k},\dots,p_{jk}$ (where $j&lt;n$). 

Write $$p_{1k}^{\alpha_{1k}}p_{2k}^{\alpha_{2k}}\dots p_{jk}^{\alpha_{jk}}=c+k&gt;c&gt;n^{n-1}$$ Since there are at most $n-1$ factors $p_{ik}^{\alpha_{ik}}$, at least one of them must be $&gt;n$. Thus for each $c+k$ with fewer than $n$ prime factors we can choose at least one factor $p_{ik}^{\alpha_{ik}}&gt;n$. If it were possible to choose the same prime power in two cases, say for $c+k$ and $c+j$ with $k&gt;j$, then the smaller of the two powers $p^{\lambda}&gt;n$ would divide the difference $c+k-(c+j)=k-j&lt;n$, an impossibility. Thus a different prime can be associated with each number $c+k$ in all cases and the proof is complete.
As others pointed out, what I wrote earlier did not work, and I spent several hours failing to fix it. But a correct solution turns out to be already published.

@JeppeStigNielsen [Comment under question] pointed out that this is related to Grimm's Conjecture. Grimm's Conjecture is similar but with the requirement that $c&gt;n^{n-1}$ replaced by the requirement that the $n$ numbers $c+1,\dots,c+n$ be composite.

But in his original paper (American Mathematical Monthly 76 (1969) p1126), he proves the result above. The proof is quite short:

Consider the prime factoring of $c+1,\dots,c+n$. If $c+k$ is divisible by more than $n-1$ distinct primes, then no matter what primes are factored from the other $n-1$ numbers $c+j$ there would be a prime to factor from $c+k$. Hence we assume $c+k$ has fewer than $n$ distinct prime factors $p_{1k},\dots,p_{jk}$ (where $j&lt;n$). 

Write $$p_{1k}^{\alpha_{1k}}p_{2k}^{\alpha_{2k}}\dots p_{jk}^{\alpha_{jk}}=c+k&gt;c&gt;n^{n-1}$$ Since there are at most $n-1$ factors $p_{ik}^{\alpha_{ik}}$, at least one of them must be $&gt;n$. Thus for each $c+k$ with fewer than $n$ prime factors we can choose at least one factor $p_{ik}^{\alpha_{ik}}&gt;n$. If it were possible to choose the same prime power in two cases, say for $c+k$ and $c+j$ with $k&gt;j$, then the smaller of the two powers $p^{\lambda}&gt;n$ would divide the difference $c+k-(c+j)=k-j&lt;n$, an impossibility. Thus a different prime can be associated with each number $c+k$ in all cases and the proof is complete.