5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Are $p,q$ distinct? $\endgroup$ – Toby Mak Jul 6 '17 at 11:42
  • $\begingroup$ 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.). $\endgroup$ – lulu Jul 6 '17 at 11:42
  • $\begingroup$ 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. $\endgroup$ – Toby Mak Jul 6 '17 at 11:45
8
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ you can also say that at least one, of p and q, have to be below 1000 though. $\endgroup$ – user451844 Jul 6 '17 at 13:01
  • $\begingroup$ @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. $\endgroup$ – M. Winter Jul 6 '17 at 13:01
  • 1
    $\begingroup$ 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. $\endgroup$ – user451844 Jul 6 '17 at 13:06
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ If I have misconstrued the question please advise. Perhaps there is an error in my program? $\endgroup$ – daniel Jul 6 '17 at 19:44
  • 2
    $\begingroup$ 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$. $\endgroup$ – lhf Jul 6 '17 at 21:21
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.