# Thread: Prime number sum

1. ## Prime number sum

From a proof I have reason to believe the following inequality holds

$\displaystyle \displaystyle \sum_{\substack{ p\leq x \\ p| q}} 1 \ll \log q$

where p signifies summing only over primes. But I cannot prove it.

(The full argument used is: $\displaystyle \displaystyle \sum_{\substack{ p\leq x \\ p| q}} \bigg[\frac{\log x}{\log p}\bigg]\log p \ll (\log x)\log q$ )

2. If I understand correctly, you are trying to bound the number of distinct prime divisors for a number $\displaystyle q$ by $\displaystyle \log q$? If this is correct, then you can find a loose bound on the number of distinct prime divisors.

Take $\displaystyle k$ such that $\displaystyle 2^{k-1}\leq q< 2^k$. Then, $\displaystyle q$ can have at most $\displaystyle k-1$ distinct prime divisors. Taking the logarithm gives $\displaystyle k-1\leq \log_2 q\leq k$. So in conclusion,

$\displaystyle \displaystyle \sum_{p|q} 1\leq k-1\leq \log_2 q$

where $\displaystyle p$ is prime. This bound is actually sharp: take $\displaystyle q=2$.