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

Le plus petit souvenir ? Ce n'est pas la plus petite, mais c'est un pas dans la bonne direction.

class PrimeDictionary {
    BitArray bits;

    public PrimeDictionary(int n) {
        bits = new BitArray(n + 1);
        for (int i = 0; 2 * i + 3 <= n; i++) {
            bits.Set(i, CheckPrimality(2 * i + 3));
        }
    }

    public PrimeDictionary(IEnumerable<int> primes) {
        bits = new BitArray(primes.Max());
        foreach(var prime in primes.Where(p => p != 2)) {
            bits.Set((prime - 3) / 2, true);
        }
    }

    public bool IsPrime(int k) {
        if (k == 2) {
            return true;
        }
        if (k % 2 == 0) {
            return false;
        }
        return bits[(k - 3) / 2];
    }
}

Bien entendu, vous devez spécifier la définition de CheckPrimality .

Answer 2

J'ai implémenté ici un testeur de primalité rapide :

primeat.zip

Il fonctionne parfaitement jusqu'à 32 bits, en utilisant la fonction pseudo-prime forte test. Il utilise des divisions anticipées via des gcds astucieux, ce qui lui permet d'être assez rapide la plupart du temps. Je l'ai comparé à un tamis complet (qui prend environ 200 Mo à stocker) pour m'assurer qu'il est correct pour l'ensemble de la gamme 32 bits.

Answer 3

Idée similaire à l'algorithme qui a été mentionné

public static boolean isPrime(int n) {

    if(n == 2 || n == 3) return true;
    if((n & 1 ) == 0 || n % 3 == 0) return false;
    int limit = (int)Math.sqrt(n) + 1;
    for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) {
        if(n % i == 0) return false;
        numChecks++;
    }
    return true;
}

Answer 4

Trouver si le ou les nombres d'une plage sont premiers.

#!usr/bin/python3

def prime_check(*args):
    for arg in args:
        if arg > 1:     # prime numbers are greater than 1
            for i in range(2,arg):   # check for factors
                if(arg % i) == 0:
                    print(arg,"is not Prime")
                    print(i,"times",arg//i,"is",arg)
                    break
            else:
                print(arg,"is Prime")

            # if input number is less than
            # or equal to 1, it is not prime
        else:
            print(arg,"is not Prime")
    return

# Calling Now
prime_check(*list(range(101)))  # This will check all the numbers in range 0 to 100 
prime_check(#anynumber)         # Put any number while calling it will check.

Answer 5

myInp=int(input("Enter a number: "))
if myInp==1:
    print("The number {} is neither a prime not composite no".format(myInp))
elif myInp>1:
    for i in range(2,myInp//2+1):
        if myInp%i==0:
            print("The Number {} is not a prime no".format(myInp))
            print("Because",i,"times",myInp//i,"is",myInp)
            break
    else:
        print("The Number {} is a prime no".format(myInp))
else:
    print("Alas the no {} is a not a prime no".format(myInp))