Misplaced Pages

Prime-counting function: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 23:41, 28 December 2004 edit68.154.65.92 (talk)No edit summary← Previous edit Revision as of 05:01, 6 January 2005 edit undo68.154.73.90 (talk) revert removing uncited formulaNext edit →
Line 1: Line 1:
#REDIRECT ]
In ], a '''prime-counting function''' is any of many methods that count ].

Historically there are several such methods. Traditionally the prime counting function is given as <math>\pi(x)</math>, for instance, <math>\pi(1000)=168</math> as there are 168 primes up to 1000.

Prime counting itself has been eclipsed by research on the ] formulated by ].

His work was a continuation of research relating prime numbers to ] that included important figures like ] who along with others noticed that

:<math>\pi(x)\approx\frac{x}{\ln(x)}</math>

which lead to the relation known as the ] where an important figure in the history before Riemann is ] who used the ] ], which Riemann expanded into the ] by ] to get the ].

One compact method for actually counting primes is the following ]:

With ] x and y, if <math>y\le\sqrt{x}</math> then

:<math>p(x,y) = \mathrm{floor}(x) - 1 -\sum_{k=2}^y {((p(x/k,k-1) - p(k-1,\sqrt{k-1}))( p(k,\sqrt{k}) - p(k-1,\sqrt{k-1})))}</math>

else <math>p(x,y) = p(x,\sqrt{x})</math>.

Here <math>\pi(x) = p(x,\sqrt{x})</math> gives the count of prime numbers.

The method relies on the ] as well as a few other ideas, and bears remarkable similarities to other less compactly represented prime counting functions, like ] discovered by the French mathematicians ] and ] discovered by the German mathematician ].

The ] summation is of a ] with the constraint that <math>y\le\sqrt{x}</math>.

The method finds prime numbers as it recurses, and far faster ] can be developed from it by instead using a ] like the ] to get the prime numbers up to <math>\sqrt{x}</math> versus letting the formula find them.

Some values calculated for this article from one such algorithm:
{| border=1
|<math>p(10,3)</math>
|4
|-
|<math>p(100,10)</math>
|25
|-
|<math>p(1000,31)</math>
|168
|-
|<math>p(10000,100)</math>
|1229
|-
|<math>p(10^5,316)</math>
|9592
|-
|<math>p(10^6,1000)</math>
|78498
|-
|<math>p(10^7,3162)</math>
|664579
|-
|<math>p(10^8,10^4)</math>
|5761455
|-
|<math>p(10^9,31622)</math>
|50847534
|-
|<math>p(10^{10},10^5)</math>
|455052511
|-
|<math>p(10^{11},316227)</math>
|4118054813
|-
|<math>p(10^{12},10^6)</math>
|37607912018
|}


''See also'': ]

{{stub}}


]

Revision as of 05:01, 6 January 2005

Redirect to: