J'ai une gamme de nombres aléatoires et je dois retourner les nombres premiers de ce tableau. Je suis familière avec la solution root (n) (n étant ce numéro particulier, pas la taille de la matrice). Je ne peux pas appliquer le tamis d'eratosthènes car cela fonctionne avec des chiffres dans certaines gammes, mais les chiffres sont complètement aléatoires.
Merci de me corriger si je manque quelque chose. Merci d'avance!
3 Réponses :
Si l'espace est important et que vous connaissez C ++, vous pouvez utiliser Bitset au lieu de BOOL qui serait une amélioration 8 fois, car BOOL utilise 8 bits pour un élément, tandis que Bitset n'utilise qu'un bit pour stocker une valeur de 1 ou 0 ;
Vous pouvez réduire de moitié la taille de Prime en maintenant les numéros impairs et en traitant 2 séparément dans isprime () .
Vous recherchez un test de primalité. Vous devriez être capable de rechercher et de trouver beaucoup de possibilités. Voici une réponse que j'ai écrite il y a quelques années, c'est probablement beaucoup plus que ce que vous voulez:
Le moyen le plus rapide de Trouvez si un numéro donné est préféré
La plupart des détails Il y a pour chiffres de plus de 64 bits où il y a beaucoup de digressions et de choix possibles. Pour les entrées 64 bits, la réponse simple et raisonnable consiste à utiliser une petite division d'essai suivie d'un ensemble artisanal de tests Miller-Rabin qui donnent des résultats déterministes (il n'ya à la fois aucun aléatoire utilisé et aucune éventuelle d'erreur si elle est correctement mise en œuvre). Si vous souhaitez optimiser un peu, il y a des ensembles hachés et BPSW à prendre en compte.
addendum : il existe des cas qui pourraient être effectués plus rapidement si le nombre d'entrées est beaucoup plus grand que la taille d'entrée maximale ou le nombre d'entrées uniques, ou s'il existe une certaine distribution telle qu'une attente de nombreuses entrées répétées. Ensuite, des solutions telles que la mise en cache ou la génération d'un bitset pour une recherche rapide pourraient être plus rapides. La connaissance du jeu d'entrée aide beaucoup.
Chaque numéro principal est adjacent à 6n (où N> = 1).
friston Vérifiez qu'un numéro est adjacent à plusieurs de 6.
Si le numéro est adjacent, appliquez l'algorithme de test de primalité sur ce numéro. Justification pour la méthode 6n: https://www.youtube.com/watch?v=zmkiIFS35HQ
Obtenez le maximum de l'entrée et utilisez le tamis jusqu'à ce numéro, ou simplement le résoudre individuellement pour chaque numéro. Quel est le problème?
Nous ne devons-nous pas utiliser d'espace supplémentaire (comme HASH) pour stocker toutes les primes à l'aide de tamis, puis vérifiez si le numéro donné est présent? Je veux le faire sans utiliser de l'espace.
"sans utiliser de l'espace" : cela n'est pas mentionné dans votre question. Au contraire, vous nous dites que vous avez considéré le tamis, mais le rejeté, non pas parce qu'il a besoin d'espace, mais que les chiffres sont aléatoires.
Je suis familier avec la solution root (n) Je ne peux même pas dire si je suis: veuillez le croquisser dans votre message.