The definition says that for any number N, N is almost prime if it doesn't have any prime numbers less than $(log_2N)^2$. I'm trying to show that there exists a composite number such that it is almost prime.

This is my attempt at showing this:

Let $N = ab$ be a composite number for any integers $a$ and $b$. By the Fundamental Theorem of Arithmetic, we can express $a$ and $b$ as follows:

$a=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$ and $b=p_1^{\beta_1}p_2^{\beta_2}...p_k^{\beta_k}$, where r and k are positive integers, and $\alpha_i, \beta_i \ge 0$ for all $i\in{[1...k]}$.

If N is an almost prime number, then for all $i\in[1...k]$, $p_i \ge(log_2N)^2$.

From there, I have absolutely no idea on what to do next. I'm also curious on what the intuition is for using $(log_2N)^2$ in the definition, like where does it come from?

I appreciate it if someone could help me out with this. Thank you advance.

  • $\begingroup$ If $p$ is a prime, then consider $N=p^2$. For sufficiently large $N$ we have $\sqrt N>(\log_2(N) )^2$. $\endgroup$ – lulu Apr 2 at 11:34
  • $\begingroup$ $N=257^2$ is one such number. The problem would have been more interesting if you insisted on findig one such number that is not a perfect square. $\endgroup$ – Oldboy Apr 2 at 12:12
  • 1
    $\begingroup$ You can take $N=pq$ such that $2^{n-1}<p,q<2^{n+1}$ then for $n\geq 11$ it works for every such p, q. $\endgroup$ – kingW3 Apr 2 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.