All squarefree semiprime numbers that less than a certain number

174 Views Asked by At

How can i find all number $N$, where $N=p*q$. (Here, $p$ and $q$ are primes and $p<q$) ?

For example: I want a formula that help me to find all $N<1000$

2

There are 2 best solutions below

1
On

For each prime $p < \sqrt{1000}$, you take $pq$ for each prime $q$ with $p < q < 1000/p$.

EDIT: As requested, here is some Matlab code.

A = tril(primes(500)' * primes(sqrt(1000)),-1);
sort(A(A > 0 & A < 1000)')
0
On

Apply the sieve of sundaram's logic, $$(2a+1)(2b+1)=2(2ab+a+b)+1$$ one of $a,b$ must less than 16, because if not $a=b$ gives $$4a^2+4a+1>1000$$ Then applying it again you'll need $c$ less than 3, because you can sieve out all values that would not create primes in the product. Finally you would double all primes less than 500.