# 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.

• Are $p,q$ distinct? – Toby Mak Jul 6 '17 at 11:42
• Are you asking for an exact answer? If so I don't think there's anything to be done but straight computation (easy if you have a list of all primes less than your target, or in this case less than half your target.). – lulu Jul 6 '17 at 11:42
• These numbers are called semiprimes - if you know how to code you can use this Rosetta Code page (rosettacode.org/wiki/Semiprime) for reference on how to count the number of semiprimes. – Toby Mak Jul 6 '17 at 11:45

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.

• you can also say that at least one, of p and q, have to be below 1000 though. – user451844 Jul 6 '17 at 13:01
• @RoddyMacPhee There are probably many optimizations possible. But this executed surprisingly fast. So I stopped there. Also, I only control the size of $p$. If I want to control the size of $q$ I cannot use $\pi(x)$. What I can do is only use $p< 1000$ and then multiply by $2$, but still taking care not counting pairs $(p,p)$ twice. – M. Winter Jul 6 '17 at 13:01
• yeah well this one just follows logically. let p and q both be greater than 1000 then: pq = (1000a)(1000b) =1000000ab a,b>1 which is greater than 1 million. – user451844 Jul 6 '17 at 13:06

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.$

• If I have misconstrued the question please advise. Perhaps there is an error in my program? – daniel Jul 6 '17 at 19:44
• The question asks for ordered pairs and so counts $pq$ and $qp$ as different solutions but $p^2$ as only one solution. Therefore, you're both right because $2\cdot 210035-168 = 419902$, where $168$ is the number of primes less than $1000$. – lhf Jul 6 '17 at 21:21

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.