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

bool isPrime(int n) {
if(n <= 3)
    return (n > 1)==0? false: true;
else if(n%2 == 0 || n%3 == 0)
    return false;

int i = 5;

while(i * i <= n){
    if(n%i == 0 || (n%(i+2) == 0))
        return false;
    i = i + 6;
}

return true;
}

Pour n'importe quel nombre, le nombre minimum d'itérations pour vérifier si le nombre est premier ou non peut être compris entre 2 et la racine carrée du nombre. Pour réduire encore le nombre d'itérations, nous pouvons vérifier si le nombre est divisible par 2 ou 3, car les nombres maximums peuvent être éliminés en vérifiant si le nombre est divisible par 2 ou 3. En outre, tout nombre premier supérieur à 3 peut être exprimé par 6k+1 ou 6k-1. L'itération peut donc aller de 6k+1 à la racine carrée du nombre.

Answer 2

### is_prime(number) = 
### if number % p1 !=0 for all p1(prime numbers)  < (sqrt(number) + 1), 
### filter numbers that are not prime from divisors

import math
def check_prime(N, prime_numbers_found = [2]):
    if N == 2:
        return True
    if int(math.sqrt(N)) + 1 > prime_numbers_found[-1]:
        divisor_range = prime_numbers_found + list(range(prime_numbers_found[-1] + 1, int(math.sqrt(N)) + 1+ 1))
    else:
        divisor_range = prime_numbers_found
    #print(divisor_range, N)

    for number in divisor_range:
        if number not in prime_numbers_found:
             if check_prime(number, prime_numbers_found):
                prime_numbers_found.append(number)
                if N % number == 0:
                    return False
        else:
            if N % number == 0:
                return False

    return True

Answer 3

MEILLEURE SOLUTION

Je ne suis pas sûr de comprendre le concept de Time complexity: O(sqrt(n)) y Space complexity: O(1) dans ce contexte, mais le fonction prime(n) est probablement le fastest way (least iterations) pour calculer si un nombre est un nombre premier de n'importe quelle taille.

https://github.com/ganeshkbhat/fastprimenumbers

Il s'agit probablement de la MEILLEURE solution sur l'internet à ce jour 11 mars 2022. Les commentaires et l'utilisation sont les bienvenus.

Ce même code peut être appliqué dans n'importe quel langage comme C, C++, Go Lang, Java, .NET, Python, Rust, etc. avec la même logique et présenter des performances. Il est assez rapide. Je n'ai jamais vu cela mis en œuvre auparavant et cela a été fait au niveau national.

Si vous vous intéressez à la vitesse et à la performance, voici les informations suivantes """BEST""" Je peux vous donner une solution pleine d'espoir :

Itérations maximales 16666 pour n == 100000 au lieu des 100000 de la méthode conventionnelle manière

Les codes sont également disponibles ici : https://github.com/ganeshkbhat/fastprimecalculations

Si vous l'utilisez dans le cadre de votre projet, veuillez consacrer 2 minutes de votre temps à m'en informer en m'envoyant un courriel ou en enregistrant un problème sur Github avec l'objet suivant [User] ou star mon projet Github. Mais faites-le moi savoir ici https://github.com/ganeshkbhat/fastprimecalculations . J'aimerais connaître les fans et les utilisateurs de la logique du code.

def prime(n):
    if ((n == 2 or n == 3 or n == 5 or n == 7)):
        return True

    if (n == 1 or ((n > 7) and (n % 5 == 0 or n % 7 == 0 or n % 2 == 0 or n % 3 == 0))):
        return False

    if ( type((n - 1) / 6) == int or type((n + 1) / 6) == int):
        for i in range(1, n):
            factorsix = (i * 6)
            five = n / (5 + factorsix)
            seven = n / (7 + factorsix)
            if ( ((five > 1) and type(five) == int) or ((seven > 1) and type(five) == int) ):
                return False;

            if (factorsix > n):
                break;
        return True
    return False

Voici une analyse de tous les modes de calcul :

Méthode conventionnelle de vérification de la primauté :

def isPrimeConventionalWay(n):
    count = 0
    if (n <= 1):
        return False;
    # Check from 2 to n-1
    # Max iterations 99998 for n == 100000 
    for i in range(2,n):
        # Counting Iterations
        count += 1
        if (n % i == 0):
            print("count: Prime Conventional way", count)
            return False;
    print("count: Prime Conventional way", count)
    return True;

La méthode SQUAREROOT permet de vérifier l'existence d'une prime :

def isPrimeSquarerootWay(num):
    count = 0
    # if not is_number num return False
    if (num < 2):
        print("count: Prime Squareroot way", count)
        return False

    s = math.sqrt(num)
    for  i in range(2, num):
        # Counting Iterations
        count += 1
        if (num % i == 0):
            print("count: Prime Squareroot way", count)
            return False
    print("count: Prime Squareroot way", count)
    return True

AUTRES MOYENS :

def isprimeAKSWay(n):
    """Returns True if n is prime."""
    count = 0
    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:
        count += 1
        if n % i == 0:
            print("count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way", count)
            return False

        i += w
        w = 6 - w
    print("count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way", count)
    return True

Méthode SUGGÉRÉE de vérification de l'amorce :

def prime(n):
    count = 0
    if ((n == 2 or n == 3 or n == 5 or n == 7)):
        print("count: Prime Unconventional way", count)
        return True

    if (n == 1 or ((n > 7) and (n % 5 == 0 or n % 7 == 0 or n % 2 == 0 or n % 3 == 0))):
        print("count: Prime Unconventional way", count)
        return False

    if (((n - 1) / 6).is_integer()) or (((n + 1) / 6).is_integer()):
        for i in range(1, n):
            # Counting Iterations
            count += 1
            five = 5 + (i * 6)
            seven = 7 + (i * 6)
            if ((((n / five) > 1) and (n / five).is_integer()) or (((n / seven) > 1) and ((n / seven).is_integer()))):
                print("count: Prime Unconventional way", count)
                return False;

            if ((i * 6) > n):
                # Max iterations 16666 for n == 100000 instead of 100000
                break;

        print("count: Prime Unconventional way", count)
        return True

    print("count: Prime Unconventional way", count)
    return False

Tests à comparer avec la méthode traditionnelle de vérification des nombres premiers.

def test_primecalculations():
    count = 0
    iterations = 100000
    arr = []
    for i in range(1, iterations):
        traditional = isPrimeConventionalWay(i)
        newer = prime(i)
        if (traditional == newer):
            count = count + 1
        else:
            arr.push([traditional, newer, i])
    print("[count, iterations, arr] list: ", count, iterations, arr)
    if (count == iterations):
        return True
    return False

# print("Tests Passed: ", test_primecalculations())

Vous verrez les résultats du comptage du nombre d'itérations comme ci-dessous pour check of prime number: 100007 :

print("Is Prime 100007: ", isPrimeConventionalWay(100007))
print("Is Prime 100007: ", isPrimeSquarerootWay(100007))
print("Is Prime 100007: ", prime(100007))
print("Is Prime 100007: ", isprimeAKSWay(100007))

count: Prime Conventional way 96
Is Prime 100007:  False
count: Prime Squareroot way 96
Is Prime 100007:  False
count: Prime Unconventional way 15
Is Prime 100007:  False
count: Prime AKS - Mersenne primes - Fermat's little theorem or whatever way 32
Is Prime 100007:  False

Voici quelques tests de performance et les résultats ci-dessous :

import time
isPrimeConventionalWayArr = []
isPrimeSquarerootWayArr = []
primeArr = []
isprimeAKSWayArr = []

def tests_performance_isPrimeConventionalWayArr():
    global isPrimeConventionalWayArr
    for i in range(1, 1000000):
        start = time.perf_counter_ns()
        isPrimeConventionalWay(30000239)
        end = time.perf_counter_ns()
        isPrimeConventionalWayArr.append(end - start)
tests_performance_isPrimeConventionalWayArr()

def tests_performance_isPrimeSquarerootWayArr():
    global isPrimeSquarerootWayArr
    for i in range(1, 1000000):
        start = time.perf_counter_ns()
        isPrimeSquarerootWay(30000239)
        end = time.perf_counter_ns()
        isPrimeSquarerootWayArr.append(end - start)
tests_performance_isPrimeSquarerootWayArr()

def tests_performance_primeArr():
    global primeArr
    for i in range(1, 1000000):
        start = time.perf_counter_ns()
        prime(30000239)
        end = time.perf_counter_ns()
        primeArr.append(end - start)
tests_performance_primeArr()

def tests_performance_isprimeAKSWayArr():
    global isprimeAKSWayArr
    for i in range(1, 1000000):
        start = time.perf_counter_ns()
        isprimeAKSWay(30000239)
        end = time.perf_counter_ns()
        isprimeAKSWayArr.append(end - start)
tests_performance_isprimeAKSWayArr()  

print("isPrimeConventionalWayArr: ", sum(isPrimeConventionalWayArr)/len(isPrimeConventionalWayArr))
print("isPrimeSquarerootWayArr: ", sum(isPrimeSquarerootWayArr)/len(isPrimeSquarerootWayArr))
print("primeArr: ", sum(primeArr)/len(primeArr))
print("isprimeAKSWayArr: ", sum(isprimeAKSWayArr)/len(isprimeAKSWayArr))

Échantillon 1 million d'itérations

Itération 1 :

isPrimeConventionalWayArr:  1749.97224997225
isPrimeSquarerootWayArr:  1835.6258356258356
primeArr (suggested):  475.2365752365752
isprimeAKSWayArr:  1177.982377982378

Itération 2 :

isPrimeConventionalWayArr:  1803.141403141403
isPrimeSquarerootWayArr:  2184.222484222484
primeArr (suggested):  572.6434726434726
isprimeAKSWayArr:  1403.3838033838033

Itération 3 :

isPrimeConventionalWayArr:  1876.941976941977
isPrimeSquarerootWayArr:  2190.43299043299
primeArr (suggested):  569.7365697365698
isprimeAKSWayArr:  1449.4147494147494

Itération 4 :

isPrimeConventionalWayArr:  1873.2779732779734
isPrimeSquarerootWayArr:  2177.154777154777
primeArr (suggested):  590.4243904243905
isprimeAKSWayArr:  1401.9143019143019

Itération 5 :

isPrimeConventionalWayArr:  1891.1986911986912
isPrimeSquarerootWayArr:  2218.093218093218
primeArr (suggested):  571.6938716938716
isprimeAKSWayArr:  1397.6471976471976

Itération 6 :

isPrimeConventionalWayArr:  1868.8454688454688
isPrimeSquarerootWayArr:  2168.034368034368
primeArr (suggested):  566.3278663278663
isprimeAKSWayArr:  1393.090193090193

Itération 7 :

isPrimeConventionalWayArr:  1879.4764794764794
isPrimeSquarerootWayArr:  2199.030199030199
primeArr (suggested):  574.055874055874
isprimeAKSWayArr:  1397.7587977587978

Itération 8 :

isPrimeConventionalWayArr:  1789.2868892868894
isPrimeSquarerootWayArr:  2182.3258823258825
primeArr (suggested):  569.3206693206694
isprimeAKSWayArr:  1407.1486071486072

Answer 4

Lorsque je dois effectuer une vérification rapide, j'écris ce code simple basé sur la division de base entre les nombres inférieurs à la racine carrée de l'entrée.

def isprime(n):
    if n%2==0:
        return n==2
    else:
        cota = int(n**0.5)+1
        for ind in range(3,2,cota):
            if n%ind==0:
                print(ind)
                return False
    is_one = n==1
    return True != is_one

isprime(22783)

• Le dernier True != n==1 est d'éviter le cas n=1 .