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, 2019 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$
    – Saša
    Apr 2, 2019 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, 2019 at 16:58

1 Answer 1


As pointed out by some comments, this is an easy problem. The following (very inefficient) R code provides you hunderds of examples:

is.prime <- function(num) {
  if (num == 2) {
  } else if (any(num %% 2:(num-1) == 0)) {
  } else { 

maxnum = 10000
dif <- numeric(maxnum)
for(i in 1:maxnum) {
  if(is.prime(i)) {
   dif[i] <- i - log(i^2, base=2)^2 #We don't even bother with non-primes


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .