How many pairs of primes are there such that $pq < 10^6$ I'm trying to implement this function in my program, so I think that I should find that the number of pairs $$(p, q)$$ such that both p, q are prime numbers and: $$p\cdot q < 10^6$$
I'm not really good in number theory, I know that there are $78498$ primes under one million, but I know that only some of those primes form combinations that are less that one million.
Thanks in advance.
 A: There are
$$\sum_{\substack{p\text{ prim}\\p\,\le\, 10^6}}\pi\left(\frac{10^6}p\right)=419902$$
pairs, where $\pi(x)$ is the prime counting function. $10^6$ is not the product of two primes. So it suffices to count for every prime $p\le 10^6$ the number of primes $q$ less or equal $10^6/p$, because then $pq<10^6$. Actually, we only have to check $p\leq 10^6/2$ as the smallest other prime to multiply with is $2$. 
I chose this form above because this was actually feasible to calculate on my computer using Mathematica. Mathematica certainly implements an efficient version of $\pi(x)$.

Here is an even faster version to execute (motivated by Roddy):
$$2\cdot\sum_{\substack{p\text{ prim}\\p\,\le\, 1000}}\pi\left(\frac{10^6}p\right)-\pi(1000)^2=419902.$$
It uses that at least one factor has to be at most $1000=\sqrt{10^6}$. So we sum only over primes $p\le 1000$. The factor $2$ then account for the flipped version $(p,q)\to(q,p)$. As this counts everything twice with $p,q\le 1000$, we have to subtract this in the end.
A: The number of numbers less than 1000000 with k prime factors are: 
k=1: 78498, k=2: 210035, 3: 250853, 4:198062, 5:124465,6: 68963, 7: 35585, 8: 17572, 9: 8491, 
10: 4016, 11: 1878, 12: 865, 13: 400, 14: 179, 15: 79, 16: 35, 17: 14, 18: 7, 19:  2.  
The number of near-primes $pq\leq 10^6 = 210035.$ 
Basically you have to write a program to count the number of primes in each number and sort through them. The generalized prime number theorem gives a quick estimate which is good for k small compared to $\log_2 n.$
A: Just make a list of prime numbers upto $5\times10^5$ let it be $l_1$.
Create a list to store $p$ and $q$ let it be $l_2$.
Iterate over the list of prime element  and let the element you get by each iteration be $p$.
Enter $l_1$ by removing all elements less than $p$ to a function along with $l_2$, the work of function is given below -
Iterate over list starting from $p$ and let the element you get each time be $q$.
Check at every step if $pq$ is less than million if it is than store $p$ and $q$ in the list and if it is not than break.
