title: Zeef van Legendre
text: In de getaltheorie, een deelgebied van de wiskunde, is de zeef van Legendre (vernoemd naar Adrien-Marie Legendre) de  eenvoudigste methode uit de moderne zeeftheorie. Het past het concept van de zeef van Eratosthenes toe om de boven- of ondergrenzen van het aantal priemgetallen binnen een gegeven verzameling van gehele getallen te vinden. Omdat het een eenvoudige uitbreiding van idee achter de zeef van Eratosthenes is, wordt het soms ook wel de zeef van Eratosthenes-Legendre genoemd.
  
  Identiteit van Legendre
  Het centrale idee van de methode komt tot uitdrukking in de volgende identiteit die soms de identiteit van Legendre wordt genoemd:
  
  waar A een verzameling van gehele getallen is, P het product van de verschillende priemgetallen,  de Möbiusfunctie, en  de verzameling van gehele getallen in A is, die deelbaar is door d, en S(A, P) wordt gedefinieerd als:
  
  dat wil zeggen dat S(A, P) het aantal getallen in A is zonder gemeenschappelijke factoren met P.
  
  Note that in the most typical case, A is all integers less than or equal to some real number X, P is the product of all primes less than or equal to some integer z < X, and then the Legendre identity becomes:
  
  Merk op dat in het meest typische geval A gelijk is aan het aantal gehele getallen kleiner dan of gelijk aan enig reëel getal X, P het product is van alle priemgetallen kleiner dan of gelijk aan enig geheel getal z < X. De identiteit van Legendre wordt dan
  
  (waar  de vloerfunctie aangeeft). In dit voorbeeld is het feit dat de identiteit van Legendre wordt afgeleid van de zeef van Eratosthenes duidelijk: de eerste term is het aantal gehele getallen kleiner dan X, de tweede term verwijdert de veelvouden van alle priemgetallen, de derde term telt er weer de veelvouden van twee priemgetallen bij (deze waren ten onrechte "tweemaal weggestreept), en zo verder totdat alle 
   
  
  combinaties van priemgetallen zijn afgelopen. ( staat hier voor het aantal priemgetallen kleiner dan z)
  
  Wanneer S(A, P) voor dit speciale geval is uitgerekend kan het resultaat worden gebruikt om  te begrenzen door gebruik te maken van de uitdrukking
  
  wat onmiddellijk volgt uit de definitie van S(A, P).
  
  Beperkingen
  Helaas heeft de zeef van Legendre een probleem met fractionele delen van termen die in een grote fout accumuleren. waardoor de zeef in de meeste gevallen slechts zeer zwakke grenzen geeft. Daarom wordt de zeef van Legendre in de praktijk bijna nooit gebruikt. Zij is vervangen door andere technieken zoals de zeef van Brun en zeef van Selberg. Aangezien deze krachtigere zeven echter uitbreidingen zijn van de basisideeën van de zeef van Legendre, is het nuttig om eerst te begrijpen hoe de zeef van Legendre werkt.
  
  Voetnoten
  
  Bronvermelding
   
  
  Zeeftheorie