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

public static boolean isPrime(int number) {
 if(number < 2)
   return false;
 else if(number == 2 || number == 3)
        return true;
      else {
        for(int i=2;i<=number/2;i++)
           if(number%i == 0)
             return false;
           else if(i==number/2)
                return true;
      }
    return false;
}

Answer 2

La plupart des réponses précédentes sont correctes, mais voici une autre façon de vérifier si un nombre est un nombre premier. En guise de rappel, nombres premiers sont des nombres entiers supérieurs à 1 dont les seuls facteurs sont 1 et lui-même. source )

Solution :

Typiquement, vous pouvez construire une boucle et commencer à tester votre nombre pour voir s'il est divisible par 1, 2, 3 ...jusqu'au nombre que vous testez ...etc mais pour réduire le temps de vérification, vous pouvez diviser votre nombre par la moitié de sa valeur parce qu'un nombre ne peut pas être exactement divisible par quoi que ce soit au-dessus de la moitié de sa valeur. Par exemple, si vous voulez vérifier que 100 est un nombre premier, vous pouvez faire une boucle jusqu'à 50.

Code actuel :

def find_prime(number):
    if(number ==1):
        return False
    # we are dividiing and rounding and then adding the remainder to increment !
    # to cover not fully divisible value to go up forexample 23 becomes 11
    stop=number//2+number%2
    #loop through up to the half of the values
    for item in range(2,stop):
        if number%item==0:
           return False
        print(number)
    return True

if(find_prime(3)):
    print("it's a prime number !!")
else:
    print("it's not a prime")

Answer 3

Nous pouvons utiliser les flux Java pour mettre en œuvre cette méthode en O(sqrt(n)) ; Considérons que noneMatch est une méthode de court-circuitage qui arrête l'opération lorsqu'elle s'avère inutile pour déterminer le résultat :

Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(n == 2 ? "Prime" : IntStream.rangeClosed(2, ((int)(Math.sqrt(n)) + 1)).noneMatch(a -> n % a == 0) ? "Prime" : "Not Prime");

Answer 4

Avec l'aide des flux et des lambdas Java-8, il peut être mis en œuvre de cette manière en quelques lignes seulement :

public static boolean isPrime(int candidate){
        int candidateRoot = (int) Math.sqrt( (double) candidate);
        return IntStream.range(2,candidateRoot)
                .boxed().noneMatch(x -> candidate % x == 0);
    }

Les performances devraient être proches de O(sqrt(N)) . Peut-être que quelqu'un le trouvera utile.

Answer 5

Permettez-moi de vous proposer la solution idéale pour les entiers 64 bits. Désolé d'utiliser C#. Vous n'avez pas déjà spécifié qu'il s'agissait de python dans votre premier message. J'espère que vous pourrez trouver une fonction modPow simple et l'analyser facilement.

public static bool IsPrime(ulong number)
{
    return number == 2 
        ? true 
        : (BigInterger.ModPow(2, number, number) == 2 
            ? ((number & 1) != 0 && BinarySearchInA001567(number) == false) 
            : false)
}

public static bool BinarySearchInA001567(ulong number)
{
    // Is number in list?
    // todo: Binary Search in A001567 (https://oeis.org/A001567) below 2 ^ 64
    // Only 2.35 Gigabytes as a text file http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
}