Un stockage efficace de nombres premiers

Pour une bibliothèque, j'ai besoin de stocker les premiers nombres premiers les nombres jusqu'à une limite L. Cette collection doit avoir un O(1) temps de recherche (afin de vérifier si un nombre est premier ou pas) et il doit être facile, étant donné un nombre, trouver le prochain nombre premier (en supposant qu'il est plus petit que L).

Étant donné que L est fixe, un Eratostene tamis pour générer la liste est très bien. Maintenant, j'utilise un panier booléen tableau pour stocker la liste, qui ne contient que des entrées pour les nombres impairs entre 3 et L (inclus). Cela prend (L-2)/2 bits de mémoire. Je voudrais être en mesure d'augmenter de manière statique L sans utiliser plus de mémoire.

Est-il une structure de données en utilisant moins de mémoire avec des propriétés similaires? Ou au moins la constante recherche du temps? (nombres impairs peuvent ensuite être énumérés jusqu'à ce que nous obtenir une prime)

(la langue que j'ai écrit ceci en est Facteur de mais cette question serait la même dans n'importe quelle langue qui a intégré ou facilement programmable paniers bits tableaux)

  • Ce qui est un cas typique de "L'? Est-ce pour un dispositif intégré où la mémoire est serré? Elle pourrait affecter les recommandations. Étant donné qu'il y a 50,847,534 nombres premiers en vertu d'un milliard de dollars, vous pourriez passer plus de temps à l'emballage/déballage puis d'un simple tableau de 4 octets entiers.
  • L est aujourd'hui de 5 000 000.
  • Et je ne voudrais pas besoin de plus que le ~320kB de mémoire, j'ai aujourd'hui.
  • Si vous voulez stocker des informations dans l'ordre de 5 000 000 de nombres entiers dans de 320 000 octets...
  • DanielDaranas: c'est ce qui est fait aujourd'hui. Étant donné que seul un nombre impair de primalité est stocké (et prend un bit d'information, vraie ou fausse), je stocker des informations à propos de 2 500 000 nombre impair dans moins de 313 000 octets. Pourquoi cela vous surprend-il?
  • Je pense que c'est assez cool que nous pouvons compact tellement en si peu d'espace.
  • Cela me surprend parce que la contrainte de mémoire est si exigeant qu'il exclut pratiquement n'importe quelle efforts pour optimiser l'ordre des algorithmes impliqués. Il n'est pas impossible de travailler avec cette limite de mémoire, étant donné les propriétés des nombres premiers; mais il est loin, loin d'être optimale.