# How to prove that there exists a composite almost prime number?

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.

• If $p$ is a prime, then consider $N=p^2$. For sufficiently large $N$ we have $\sqrt N>(\log_2(N) )^2$.
– lulu
Apr 2, 2019 at 11:34
• $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.
– Saša
Apr 2, 2019 at 12:12
• 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. Apr 2, 2019 at 16:58

## 1 Answer

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) {
return(TRUE)
} else if (any(num %% 2:(num-1) == 0)) {
return(FALSE)
} else {
return(TRUE)
}
}

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
}
}

which(dif>0)
$$$$
`