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

L'algorithme le plus rapide pour tester les nombres premiers en général est le suivant AKS . L'article de Wikipédia le décrit en détail et renvoie à l'article original.

Si vous voulez trouver de grands nombres, examinez les nombres premiers qui ont des formes spéciales comme Premiers de Mersenne .

L'algorithme que je mets habituellement en œuvre (facile à comprendre et à coder) est le suivant (en Python) :

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

Il s'agit d'une variante du classique O(sqrt(N)) algorithme. Il utilise le fait qu'un nombre premier (sauf 2 et 3) est de la forme 6k - 1 o 6k + 1 et ne s'intéresse qu'aux diviseurs de cette forme.

Parfois, si je veux vraiment de la vitesse et la portée est limitée Je mets en œuvre un test de pseudo-primauté basé sur Petit théorème de Fermat . Si je veux vraiment gagner en rapidité (c'est-à-dire éviter complètement l'algorithme O(sqrt(N)), je pré-calcule les faux positifs (voir Carmichael ) et effectuer une recherche binaire. C'est de loin le test le plus rapide que j'aie jamais mis en œuvre, le seul inconvénient étant que la portée est limitée.

Answer 2

J'ai comparé l'efficacité des suggestions les plus populaires pour déterminer si un nombre est premier. J'ai utilisé python 3.6 en ubuntu 17.10 J'ai testé avec des nombres allant jusqu'à 100.000 (vous pouvez tester avec des nombres plus importants en utilisant mon code ci-dessous).

Ce premier graphique compare les fonctions (qui sont expliquées plus loin dans ma réponse), montrant que les dernières fonctions ne croissent pas aussi vite que la première lorsque l'on augmente les nombres.

Dans le deuxième graphique, on peut voir que le temps augmente régulièrement dans le cas des nombres premiers, mais que les nombres non premiers n'augmentent pas aussi rapidement (parce que la plupart d'entre eux peuvent être éliminés dès le début).

Voici les fonctions que j'ai utilisées :

1. cette réponse y cette réponse a suggéré une construction utilisant all() :

   def is_prime_1(n):
       return n > 1 and all(n % i for i in range(2, int(math.sqrt(n)) + 1))

2. Cette réponse a utilisé une sorte de boucle while :

   def is_prime_2(n):
       if n <= 1:
           return False
       if n == 2:
           return True
       if n == 3:
           return True
       if n % 2 == 0:
           return False
       if n % 3 == 0:
           return False
   
       i = 5
       w = 2
       while i * i <= n:
           if n % i == 0:
               return False
           i += w
           w = 6 - w
   
       return True

3. Cette réponse a inclus une version avec un for boucle :

   def is_prime_3(n):
       if n <= 1:
           return False
   
       if n % 2 == 0 and n > 2:
           return False
   
       for i in range(3, int(math.sqrt(n)) + 1, 2):
           if n % i == 0:
               return False
   
       return True

4. Et j'ai mélangé quelques idées des autres réponses pour en faire une nouvelle :

   def is_prime_4(n):
       if n <= 1:          # negative numbers, 0 or 1
           return False
       if n <= 3:          # 2 and 3
           return True
       if n % 2 == 0 or n % 3 == 0:
           return False
   
       for i in range(5, int(math.sqrt(n)) + 1, 2):
           if n % i == 0:
               return False
   
       return True

---

Voici mon script pour comparer les variantes :

import math
import pandas as pd
import seaborn as sns
import time
from matplotlib import pyplot as plt

def is_prime_1(n):
    ...
def is_prime_2(n):
    ...
def is_prime_3(n):
    ...
def is_prime_4(n):
    ...

default_func_list = (is_prime_1, is_prime_2, is_prime_3, is_prime_4)

def assert_equal_results(func_list=default_func_list, n):
    for i in range(-2, n):
        r_list = [f(i) for f in func_list]
        if not all(r == r_list[0] for r in r_list):
            print(i, r_list)
            raise ValueError
    print('all functions return the same results for integers up to {}'.format(n))

def compare_functions(func_list=default_func_list, n):
    result_list = []
    n_measurements = 3

    for f in func_list:
        for i in range(1, n + 1):
            ret_list = []
            t_sum = 0
            for _ in range(n_measurements):
                t_start = time.perf_counter()
                is_prime = f(i)
                t_end = time.perf_counter()

                ret_list.append(is_prime)
                t_sum += (t_end - t_start)

            is_prime = ret_list[0]
            assert all(ret == is_prime for ret in ret_list)
            result_list.append((f.__name__, i, is_prime, t_sum / n_measurements))

    df = pd.DataFrame(
        data=result_list,
        columns=['f', 'number', 'is_prime', 't_seconds'])
    df['t_micro_seconds'] = df['t_seconds'].map(lambda x: round(x * 10**6, 2))
    print('df.shape:', df.shape)

    print()
    print('', '-' * 41)
    print('| {:11s} | {:11s} | {:11s} |'.format(
        'is_prime', 'count', 'percent'))
    df_sub1 = df[df['f'] == 'is_prime_1']
    print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
        'all', df_sub1.shape[0], 100))
    for (is_prime, count) in df_sub1['is_prime'].value_counts().iteritems():
        print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
            str(is_prime), count, count * 100 / df_sub1.shape[0]))
    print('', '-' * 41)

    print()
    print('', '-' * 69)
    print('| {:11s} | {:11s} | {:11s} | {:11s} | {:11s} |'.format(
        'f', 'is_prime', 't min (us)', 't mean (us)', 't max (us)'))
    for f, df_sub1 in df.groupby(['f', ]):
        col = df_sub1['t_micro_seconds']
        print('|{0}|{0}|{0}|{0}|{0}|'.format('-' * 13))
        print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
            f, 'all', col.min(), col.mean(), col.max()))
        for is_prime, df_sub2 in df_sub1.groupby(['is_prime', ]):
            col = df_sub2['t_micro_seconds']
            print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
                f, str(is_prime), col.min(), col.mean(), col.max()))
    print('', '-' * 69)

    return df

Exécution de la fonction compare_functions(n=10**5) (nombres jusqu'à 100 000), j'obtiens ce résultat :

df.shape: (400000, 5)

 -----------------------------------------
| is_prime    | count       | percent     |
| all         |     100,000 |     100.0 % |
| False       |      90,408 |      90.4 % |
| True        |       9,592 |       9.6 % |
 -----------------------------------------

 ---------------------------------------------------------------------
| f           | is_prime    | t min (us)  | t mean (us) | t max (us)  |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_1  | all         |        0.57 |        2.50 |      154.35 |
| is_prime_1  | False       |        0.57 |        1.52 |      154.35 |
| is_prime_1  | True        |        0.89 |       11.66 |       55.54 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_2  | all         |        0.24 |        1.14 |      304.82 |
| is_prime_2  | False       |        0.24 |        0.56 |      304.82 |
| is_prime_2  | True        |        0.25 |        6.67 |       48.49 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_3  | all         |        0.20 |        0.95 |       50.99 |
| is_prime_3  | False       |        0.20 |        0.60 |       40.62 |
| is_prime_3  | True        |        0.58 |        4.22 |       50.99 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_4  | all         |        0.20 |        0.89 |       20.09 |
| is_prime_4  | False       |        0.21 |        0.53 |       14.63 |
| is_prime_4  | True        |        0.20 |        4.27 |       20.09 |
 ---------------------------------------------------------------------

Ensuite, en exécutant la fonction compare_functions(n=10**6) (nombres jusqu'à 1.000.000), j'obtiens ce résultat :

df.shape: (4000000, 5)

 -----------------------------------------
| is_prime    | count       | percent     |
| all         |   1,000,000 |     100.0 % |
| False       |     921,502 |      92.2 % |
| True        |      78,498 |       7.8 % |
 -----------------------------------------

 ---------------------------------------------------------------------
| f           | is_prime    | t min (us)  | t mean (us) | t max (us)  |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_1  | all         |        0.51 |        5.39 |     1414.87 |
| is_prime_1  | False       |        0.51 |        2.19 |      413.42 |
| is_prime_1  | True        |        0.87 |       42.98 |     1414.87 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_2  | all         |        0.24 |        2.65 |      612.69 |
| is_prime_2  | False       |        0.24 |        0.89 |      322.81 |
| is_prime_2  | True        |        0.24 |       23.27 |      612.69 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_3  | all         |        0.20 |        1.93 |       67.40 |
| is_prime_3  | False       |        0.20 |        0.82 |       61.39 |
| is_prime_3  | True        |        0.59 |       14.97 |       67.40 |
|-------------|-------------|-------------|-------------|-------------|
| is_prime_4  | all         |        0.18 |        1.88 |      332.13 |
| is_prime_4  | False       |        0.20 |        0.74 |      311.94 |
| is_prime_4  | True        |        0.18 |       15.23 |      332.13 |
 ---------------------------------------------------------------------

---

J'ai utilisé le script suivant pour tracer les résultats :

def plot_1(func_list=default_func_list, n):
    df_orig = compare_functions(func_list=func_list, n=n)
    df_filtered = df_orig[df_orig['t_micro_seconds'] <= 20]
    sns.lmplot(
        data=df_filtered, x='number', y='t_micro_seconds',
        col='f',
        # row='is_prime',
        markers='.',
        ci=None)

    plt.ticklabel_format(style='sci', axis='x', scilimits=(3, 3))
    plt.show()

Answer 3

On peut utiliser sympy .

import sympy

sympy.ntheory.primetest.isprime(33393939393929292929292911111111)

True

D'après les documents de Sympa. La première étape consiste à rechercher des facteurs triviaux qui, s'ils sont trouvés, permettent un retour rapide. Ensuite, si le tamis est suffisamment grand, on utilise la recherche par bissection sur le tamis. Pour les petits nombres, un ensemble de tests déterministes de Miller-Rabin est effectué avec des bases dont on sait qu'elles n'ont pas de contre-exemples dans leur intervalle. Enfin, si le nombre est supérieur à 2^64, un test BPSW fort est effectué. Bien qu'il s'agisse d'un test de prime probable et que nous pensions qu'il existe des contre-exemples, il n'y a pas de contre-exemples connus.

Answer 4

D'après Wikipedia, Le tamis d'Eratosthène tiene la complexité O(n * (log n) * (log log n)) et exige O(n) mémoire - c'est donc un bon point de départ si vous ne testez pas des nombres particulièrement élevés.

Answer 5

Il existe de nombreuses façons d'effectuer la test de primalité .

Il n'y a pas vraiment de structure de données à interroger. Si vous avez beaucoup de chiffres à tester, vous devriez probablement lancer une commande test probabiliste puisqu'ils sont plus rapides, et le faire suivre d'un test déterministe pour s'assurer que le nombre est premier.

Sachez que les mathématiques qui sous-tendent les algorithmes les plus rapides ne sont pas pour les âmes sensibles.