# Math Help - Prime number sum

1. ## Prime number sum

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

$\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 \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 $q$ by $\log q$? If this is correct, then you can find a loose bound on the number of distinct prime divisors.

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

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

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