Comment créer la cartographie la plus compacte n → isprime(n) jusqu'à une limite N ?

Question

Naturellement, pour les bool isprime(number) il y aurait une structure de données que je pourrais interroger.
I définir le meilleur algorithme est l'algorithme qui produit une structure de données ayant la plus faible consommation de mémoire pour l'intervalle (1, N), où N est une constante.
Voici un exemple de ce que je recherche : Je pourrais représenter tous les nombres impairs par un bit, par exemple pour la plage de nombres donnée (1, 10), commence à 3 : 1110

Le dictionnaire suivant peut être davantage compressé, n'est-ce pas ? Je pourrais éliminer les multiples de cinq avec un peu de travail, mais les nombres qui se terminent par 1, 3, 7 ou 9 doivent être présents dans le tableau de bits.

Comment résoudre le problème ?

Answer 1

J'ai obtenu une fonction prime qui fonctionne jusqu'à (2^61)-1 Ici :

from math import sqrt
def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1)))

Explication :

Les all() peut être redéfinie comme suit :

def all(variables):
    for element in variables:
        if not element: return False
    return True

Les all() passe simplement par une série de bools / nombres et renvoie False s'il voit 0 ou False .

Les sqrt() se contente d'exécuter la fonction Racine carrée d'un nombre.

Par exemple :

>>> from math import sqrt
>>> sqrt(9)
>>> 3
>>> sqrt(100)
>>> 10

Les num % x renvoie la partie reste de num / x.

Enfin, range(2, int(sqrt(num))) signifie qu'il créera un liste qui commence à 2 et se termine à int(sqrt(num)+1)

Pour plus d'informations sur la gamme, consultez le site suivant site web !

Les num > 1 consiste simplement à vérifier si la variable num est plus grand que 1, car 1 et 0 ne sont pas considérés comme des nombres premiers.

J'espère que cela vous a aidé :)

Answer 2

En Python :

def is_prime(n):
    return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))

Une conversion plus directe du formalisme mathématique vers Python consisterait à utiliser all(n % p != 0... ) mais cela nécessite une évaluation stricte de toutes les valeurs de p. pas n'importe lequel peut se terminer prématurément si une valeur True est trouvée.

Answer 3

Meilleur algorithme pour les nombres premiers javascript

 function isPrime(num) {
      if (num <= 1) return false;
      else if (num <= 3) return true;
      else if (num % 2 == 0 || num % 3 == 0) return false;
      var i = 5;
      while (i * i <= num) {
        if (num % i == 0 || num % (i + 2) == 0) return false;
        i += 6;
      }
      return true
    }

Answer 4

Un nombre premier est un nombre qui n'est divisible que par 1 et par lui-même. Tous les autres nombres sont appelés composite .

La façon la plus simple de trouver un nombre premier est de vérifier si le nombre saisi est un nombre composite :

    function isPrime(number) {
        // Check if a number is composite
        for (let i = 2; i < number; i++) {
            if (number % i === 0) {
                return false;
            }
        }
        // Return true for prime numbers
        return true;
    }

Le programme doit diviser la valeur de number par tous les nombres entiers à partir de 1 et jusqu'à sa valeur. Si ce nombre peut être divisé de façon égale non seulement par un et par lui-même, il s'agit d'un nombre composite.

La valeur initiale de la variable i doit être égal à 2 car les nombres premiers et les nombres composés peuvent être divisés uniformément par 1.

    for (let i = 2; i < number; i++)

Entonces i est inférieur à number pour la même raison. Les nombres premiers et composites peuvent tous deux être divisés par eux-mêmes. Il n'y a donc aucune raison de le vérifier.

Nous vérifions ensuite si la variable peut être divisée de manière égale en utilisant l'opérateur de reste.

    if (number % i === 0) {
        return false;
    }

Si le reste est nul, cela signifie que number peut être divisé de façon égale, ce qui en fait un nombre composite et le rend faux.

Si le nombre saisi ne remplit pas la condition, cela signifie qu'il s'agit d'un nombre premier et la fonction renvoie un résultat positif.

Answer 5

Vous pourriez utiliser de grands champs de bits, peut-être un tableau de nombres de 64 bits ?