2
$\begingroup$

I saw movie "the man who knew infinity"

In which ramanujan had formulated a formula to calculate number of prime numbers between a range of numbers

My teacher told me that there exist no program which can generate primes

My friend told me that someone had found a counter example of ramanujan'a formula which was billions of billion

So I want to know that did he really formulated the formula, if yes then what is it and how it works (proof required).

$\endgroup$
  • $\begingroup$ various computer programs can generate prime numbers - some of them very simple. $\endgroup$ – Cato Dec 22 '16 at 13:23
  • 2
    $\begingroup$ Your teacher told you that "there exist no program which can generate primes"??? You can tell him or her, pardon my French, that's a bunch of baloney. $\endgroup$ – barak manos Dec 22 '16 at 13:23
  • $\begingroup$ As with regards to "number of prime numbers within a given range": You can approximate the number of primes $\in[x,y]$ as $\frac{y}{\ln(y)}-\frac{x}{\ln(x)}$. There are also tighter bounds. Though I'm not familiar with the historical details, I would guess that Ramanujan had conjectured such tighter bound, which was later refuted explicitly with a counterexample (or possibly more interestingly - refuted by proving that a counterexample existed)... $\endgroup$ – barak manos Dec 22 '16 at 13:27
  • $\begingroup$ @barakmanos That really big number too' big for me to realistically care about much? :D $\endgroup$ – Simply Beautiful Art Dec 22 '16 at 13:29
  • $\begingroup$ @SimpleArt: I understand each word in your comment, but I am unable to connect them into a meaningful statement. Would you mind rephrasing it? $\endgroup$ – barak manos Dec 22 '16 at 13:35
2
$\begingroup$

This probably isn't Ramanujan's method, but its very simple:

Take each number within the given range. Take the square root of the largest number in this range. If a number is prime, it will not be divisible by any numbers smaller than the square root of this largest number.

Now, take out all the numbers divisible by $2$. Then all the numbers divisible by $3$. Then $5,7,\dots,$ all the way till you reach the square root number. The numbers you have left are prime numbers, and this is easily doable with a computer.


If you are interested in approximations though, consider the prime-counting function. One simple approximation to finding the amount of prime numbers between $x$ and $y$:

$$\frac y{\ln y}-\frac x{\ln x}$$

Better bounds exist in the link above.

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