Oczywiście, ponieważ bool isprime(number)istnieje struktura danych, do której mógłbym zapytać.
I określić najlepszy algorytm , aby być algorytm, który wytwarza strukturę danych przy najniższym zużyciu pamięci dla zakresu (1, n], gdzie N jest stała.
Tylko przykładem tego, co szukam: mogłem reprezentować każdą liczbę nieparzystą z jednym bitem np. dla danego zakresu liczb (1, 10], zaczyna się od 3:1110

Poniższy słownik można wycisnąć bardziej, prawda? Przy odrobinie pracy mógłbym wyeliminować wielokrotności pięciu, ale liczby kończące się na 1, 3, 7 lub 9 muszą znajdować się w tablicy bitów.

Jak rozwiązać ten problem?

Test pierwszości można przeprowadzić na wiele sposobów .

Tak naprawdę nie ma struktury danych, do której można by zapytać. Jeśli masz wiele liczb do przetestowania, prawdopodobnie powinieneś uruchomić test probabilistyczny, ponieważ są one szybsze, a następnie wykonać test deterministyczny, aby upewnić się, że liczba jest pierwsza.

Powinieneś wiedzieć, że matematyka stojąca za najszybszymi algorytmami nie jest dla osób o słabym sercu.

Najszybszym algorytmem do ogólnego testowania podstawowego jest AKS . Artykuł w Wikipedii opisuje to szczegółowo i zawiera linki do oryginalnego artykułu.

Jeśli chcesz znaleźć duże liczby, spójrz na liczby pierwsze, które mają specjalne formy, takie jak liczby pierwsze Mersenne'a .

Algorytm, który zwykle implementuję (łatwy do zrozumienia i kodowania) jest następujący (w Pythonie):

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

To odmiana klasycznego O(sqrt(N))algorytmu. Wykorzystuje fakt, że liczba pierwsza (z wyjątkiem 2 i 3) ma postać 6k - 1lub 6k + 1i patrzy tylko na dzielniki tej postaci.

Czasami, jeśli naprawdę chcę prędkości, a zasięg jest ograniczony , implementuję test pseudopierwszy oparty na małym twierdzeniu Fermata . Jeśli naprawdę chcę większej szybkości (tj. Całkowicie unikać algorytmu O (sqrt (N))), obliczam wstępnie fałszywe alarmy (patrz liczby Carmichaela ) i wykonuję wyszukiwanie binarne. To zdecydowanie najszybszy test, jaki kiedykolwiek wdrożyłem, jedyną wadą jest to, że zasięg jest ograniczony.

Moim zdaniem najlepszą metodą jest wykorzystanie tego, co było wcześniej.

W Ninternecie są listy pierwszych liczb pierwszych, Nsięgające co najmniej pięćdziesięciu milionów . Pobierz pliki i użyj ich, prawdopodobnie będzie to znacznie szybsze niż jakakolwiek inna metoda, którą wymyślisz.

Jeśli chcesz rzeczywiste algorytm tworzenia własnych liczb pierwszych, Wikipedia ma wszelkiego rodzaju dobrych rzeczy na temat liczb pierwszych tutaj , w tym linki do różnych sposobów, by to zrobić, a premier testów tutaj obie metody oparte na prawdopodobieństwie i szybko deterministycznych.

Należy podjąć skoordynowany wysiłek, aby znaleźć pierwszy miliard (lub nawet więcej) liczb pierwszych i umieścić je gdzieś w sieci, aby ludzie mogli przestać wykonywać tę samą pracę w kółko i ... :-)

bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip 
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}

to jest po prostu implementacja C ++ powyższego algorytmu AKS

Porównałem skuteczność najpopularniejszych sugestii, aby określić, czy liczba jest liczbą pierwszą. Użyłem python 3.6na ubuntu 17.10; Testowałem z liczbami do 100.000 (możesz przetestować z większymi liczbami, używając mojego kodu poniżej).

Ten pierwszy wykres porównuje funkcje (które są wyjaśnione w dalszej części mojej odpowiedzi), pokazując, że ostatnie funkcje nie rosną tak szybko jak pierwsza podczas zwiększania liczb.

A na drugim wykresie widzimy, że w przypadku liczb pierwszych czas rośnie równomiernie, ale liczby inne niż pierwsze nie rosną tak szybko w czasie (ponieważ większość z nich można wyeliminować wcześnie).

Oto funkcje, których użyłem:

1. ta odpowiedź i ta odpowiedź sugerowały konstrukcję wykorzystującą all():

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

2. W tej odpowiedzi użyto jakiejś pętli 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. Ta odpowiedź zawiera wersję z forpętlą:

   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. Zmieszałem kilka pomysłów z innych odpowiedzi w nowe:

   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
   

Oto mój skrypt do porównania wariantów:

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

Uruchamiając funkcję compare_functions(n=10**5)(numery do 100.000) otrzymuję takie wyjście:

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 |
 ---------------------------------------------------------------------

Następnie uruchamiając funkcję compare_functions(n=10**6)(numery do 1.000.000) otrzymuję taki wynik:

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 |
 ---------------------------------------------------------------------

Do wykreślenia wyników użyłem następującego skryptu:

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()

Według Wikipedii, Sito Eratostenesa ma złożoność O(n * (log n) * (log log n))i wymaga O(n)pamięci - więc jest to całkiem dobre miejsce na rozpoczęcie, jeśli nie testujesz szczególnie dużych liczb.

Można użyć sympy .

import sympy

sympy.ntheory.primetest.isprime(33393939393929292929292911111111)

True

Z sympy docs. Pierwszym krokiem jest poszukiwanie błahych czynników, które w przypadku ich znalezienia umożliwiają szybki zwrot. Następnie, jeśli sito jest wystarczająco duże, użyj funkcji wyszukiwania na pół. W przypadku małych liczb przeprowadza się zestaw deterministycznych testów Millera-Rabina z zasadami, o których wiadomo, że nie mają w swoim zakresie kontrprzykładów. Wreszcie, jeśli liczba jest większa niż 2 ^ 64, wykonywany jest silny test BPSW. Chociaż jest to prawdopodobny test główny i uważamy, że istnieją kontrprzykłady, nie są znane żadne kontrprzykłady

W Pythonie 3:

def is_prime(a):
    if a < 2:
        return False
    elif a!=2 and a % 2 == 0:
        return False
    else:
        return all (a % i for i in range(3, int(a**0.5)+1))

Objaśnienie: Liczba pierwsza to liczba podzielna tylko przez siebie i 1. Np .: 2,3,5,7 ...

1) jeśli a <2: jeśli „a” jest mniejsze niż 2, nie jest liczbą pierwszą.

2) elif a! = 2 i a% 2 == 0: jeśli "a" jest podzielne przez 2, to zdecydowanie nie jest liczbą pierwszą. Ale jeśli a = 2, nie chcemy tego oceniać, ponieważ jest to liczba pierwsza. Stąd warunek a! = 2

3) return all (a% i for i in range (3, int (a 0.5) +1)): ** Najpierw zobacz, co robi polecenie all () w pythonie. Zaczynając od 3 dzielimy „a” do jego pierwiastka kwadratowego (a ** 0,5). Jeśli „a” jest podzielne, wynik będzie fałszywy. Dlaczego pierwiastek kwadratowy? Powiedzmy, że a = 16. Pierwiastek kwadratowy z 16 = 4. Nie musimy obliczać do 15. Musimy tylko sprawdzić do 4, aby stwierdzić, że nie jest to liczba pierwsza.

Dodatkowo: pętla do znajdowania wszystkich liczb pierwszych w zakresie.

for i in range(1,100):
    if is_prime(i):
        print("{} is a prime number".format(i))

Python 3:

def is_prime(a):
    return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1))

W przypadku dużych liczb nie można po prostu naiwnie sprawdzić, czy liczba kandydująca N jest podzielna przez żadną z liczb mniejszych niż sqrt (N). Dostępnych jest znacznie więcej skalowalnych testów, takich jak test pierwszości Millera-Rabina . Poniżej masz implementację w pythonie:

def is_prime(x):
    """Fast implementation fo Miller-Rabin primality test, guaranteed to be correct."""
    import math
    def get_sd(x):
        """Returns (s: int, d: int) for which x = d*2^s """
        if not x: return 0, 0
        s = 0
        while 1:
            if x % 2 == 0:
                x /= 2
                s += 1
            else:
                return s, x
    if x <= 2:
        return x == 2
    # x - 1 = d*2^s
    s, d = get_sd(x - 1)
    if not s:
        return False  # divisible by 2!
    log2x = int(math.log(x) / math.log(2)) + 1
    # As long as Riemann hypothesis holds true, it is impossible
    # that all the numbers below this threshold are strong liars.
    # Hence the number is guaranteed to be a prime if no contradiction is found.
    threshold = min(x, 2*log2x*log2x+1)
    for a in range(2, threshold):
        # From Fermat's little theorem if x is a prime then a^(x-1) % x == 1
        # Hence the below must hold true if x is indeed a prime:
        if pow(a, d, x) != 1:
            for r in range(0, s):
                if -pow(a, d*2**r, x) % x == 1:
                    break
            else:
                # Contradicts Fermat's little theorem, hence not a prime.
                return False
    # No contradiction found, hence x must be a prime.
    return True

Możesz go użyć do znalezienia ogromnych liczb pierwszych:

x = 10000000000000000000000000000000000000000000000000000000000000000000000000000
for e in range(1000):
    if is_prime(x + e):
        print('%d is a prime!' % (x + e))
        break

# 10000000000000000000000000000000000000000000000000000000000000000000000000133 is a prime!

Jeśli testujesz losowe liczby całkowite, prawdopodobnie chcesz najpierw sprawdzić, czy liczba kandydująca jest podzielna przez którąkolwiek z liczb pierwszych mniejszych niż, powiedzmy, 1000, zanim zadzwonisz do Millera-Rabina. Pomoże Ci to odfiltrować oczywiste liczby inne niż liczby pierwsze, takie jak 10444344345.

O wiele za późno na przyjęcie, ale mam nadzieję, że to pomoże. Jest to istotne, jeśli szukasz dużych liczb pierwszych:

Aby przetestować duże liczby nieparzyste, należy użyć testu Fermata i / lub testu Millera-Rabina.

Te testy wykorzystują modularne potęgowanie, które jest dość drogie, do npotęgowania bitów potrzebujesz co najmniej ndużego mnożenia int i ndużego dzielenia int. Co oznacza, że ​​złożoność modularnego potęgowania wynosi O (n³).

Więc zanim użyjesz dużych dział, musisz zrobić kilka dywizji próbnych. Ale nie rób tego naiwnie, jest sposób, aby zrobić to szybko. Najpierw pomnóż przez siebie tyle liczb pierwszych, ile pasuje do słowa, którego używasz dla dużych liczb całkowitych. Jeśli używasz słów 32-bitowych, pomnóż 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 3234846615 i oblicz największy wspólny dzielnik z liczbą, którą testujesz za pomocą algorytmu Euklidesa. Po pierwszym kroku liczba jest zmniejszana poniżej rozmiaru słowa i kontynuuj algorytm bez wykonywania pełnych dużych dzieleń całkowitych. Jeśli GCD! = 1, oznacza to, że jedna z liczb pierwszych, które pomnożyłeś, dzieli liczbę, więc masz dowód, że nie jest liczbą pierwszą. Następnie kontynuuj 31 * 37 * 41 * 43 * 47 = 95041567 i tak dalej.

Gdy przetestujesz w ten sposób kilkaset (lub tysiące) liczb pierwszych, możesz wykonać 40 rund testu Millera-Rabina, aby potwierdzić, że liczba jest pierwsza, po 40 rundach możesz być pewien, że liczba jest liczbą pierwszą istnieje tylko 2 ^ -80 szans, że jest to liczba pierwsza. nie (bardziej prawdopodobne jest awarie sprzętu ...).

Mam funkcję główną, która działa do (2 ^ 61) -1 Tutaj:

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

Wyjaśnienie:

all()Funkcja może być na nowo do tego:

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

all()Funkcja po prostu przechodzi przez serię bools / liczb i zwrotów False, jeśli uzna to 0 lub False.

sqrt()Funkcja jest po prostu robi się pierwiastek kwadratowy z liczby.

Na przykład:

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

num % xCzęść zwraca pozostałą num / X.

Wreszcie range(2, int(sqrt(num)))oznacza, że ​​utworzy listę, która zaczyna się od 2 i kończy naint(sqrt(num)+1)

Więcej informacji o asortymencie znajdziesz na tej stronie !

num > 1Część jest po prostu sprawdzenie, czy zmienna numjest większa niż 1, ponieważ posiadał 1 i 0 nie są uważane liczb pierwszych.

Mam nadzieję, że to pomogło :)

W Pythonie:

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

Bardziej bezpośrednia konwersja z formalizmu matematycznego do Pythona wykorzystałaby wszystkie (n% p! = 0 ...) , ale wymaga to ścisłej oceny wszystkich wartości p. Nie lada wersja może zakończyć wcześnie, jeśli wartość True znajduje.

najlepszy algorytm javascript liczby Prime

 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
    }

import math
import time


def check_prime(n):

    if n == 1:
        return False

    if n == 2:
        return True

    if n % 2 == 0:
        return False

    from_i = 3
    to_i = math.sqrt(n) + 1

    for i in range(from_i, int(to_i), 2):
        if n % i == 0:
            return False
    return True

Liczba pierwsza to dowolna liczba podzielna tylko przez 1 i samą siebie. Wszystkie inne liczby nazywane są złożonymi .

Najprostszym sposobem znalezienia liczby pierwszej jest sprawdzenie, czy liczba wejściowa jest liczbą złożoną:

    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;
    }

Program musi podzielić wartość numberprzez wszystkie liczby całkowite od 1 do jej wartości. Jeśli ta liczba może być podzielona równo nie tylko przez jeden, a sama jest liczbą złożoną.

Początkowa wartość zmiennej imusi wynosić 2, ponieważ zarówno liczbę pierwszą, jak i liczbę złożoną można podzielić równo przez 1.

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

Wtedy ijest mniej niż numberz tego samego powodu. Liczby pierwsze i złożone można podzielić równo. Dlatego nie ma powodu, aby to sprawdzać.

Następnie sprawdzamy, czy zmienną można podzielić równo za pomocą operatora reszty.

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

Jeśli reszta wynosi zero, oznacza to, że numbermożna ją podzielić równo, a więc jest to liczba złożona i zwraca fałsz.

Jeśli wprowadzona liczba nie spełnia warunku, oznacza to, że jest liczbą pierwszą i funkcja zwraca wartość true.

Zasugeruję Ci idealne rozwiązanie dla 64-bitowych liczb całkowitych. Przepraszam, że używam C #. Nie określiłeś go jeszcze jako python w swoim pierwszym poście. Mam nadzieję, że możesz znaleźć prostą funkcję modPow i łatwo ją przeanalizować.

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
}

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;
}

dla dowolnej liczby minimalne iteracje sprawdzające, czy liczba jest pierwsza, czy nie, mogą wynosić od 2 do pierwiastka kwadratowego liczby. Aby jeszcze bardziej zmniejszyć liczbę iteracji, możemy sprawdzić, czy liczba jest podzielna przez 2 lub 3, ponieważ maksymalne liczby można wyeliminować, sprawdzając, czy liczba jest podzielna przez 2 lub 3. Ponadto każda liczba pierwsza większa niż 3 może być wyrażona jako 6k +1 lub 6k-1. Tak więc iteracja może przejść od 6k + 1 do pierwiastka kwadratowego z liczby.

Najmniejsza pamięć? To nie jest najmniejsze, ale jest krokiem we właściwym kierunku.

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];
    }
}

Oczywiście musisz określić definicję CheckPrimality.

Myślę, że jedną z najszybszych jest moja metoda.

void prime(long long int number) {
    // Establishing Variables
    long long int i = 5;
    int w = 2;
    const long long int lim = sqrt(number);

    // Gets 2 and 3 out of the way
    if (number == 1) { cout << number << " is hard to classify. \n";  return; }
    if (number == 2) { cout << number << " is Prime. \n";  return; }
    if (number == 3) { cout << number << " is Prime. \n";  return; }

    // Tests Odd Ball Factors
    if (number % 2 == 0) { cout << number << " is not Prime. \n";  return; }
    if (number % 3 == 0) { cout << number << " is not Prime. \n";  return; }

    while (i <= lim) {
        if (number % i == 0) { cout << number << " is not Prime. \n";  return; }
        // Tests Number
        i = i + w; // Increments number
        w = 6 - i; // We already tested 2 and 3
        // So this removes testing multepules of this
    }
    cout << number << " is Prime. \n"; return;
}

Podobny pomysł do wspomnianego algorytmu AKS

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;
}

Aby sprawdzić, czy liczba lub liczby w zakresie są / są liczbą pierwszą.

#!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.

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))

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;
}

Możesz spróbować czegoś takiego.

def main():
    try:
        user_in = int(input("Enter a number to determine whether the number is prime or not: "))
    except ValueError:
        print()
        print("You must enter a number!")
        print()
        return
    list_range = list(range(2,user_in+1))
    divisor_list = []
    for number in list_range:
        if user_in%number==0:
            divisor_list.append(number)
    if len(divisor_list) < 2:
        print(user_in, "is a prime number!")
        return
    else:
        print(user_in, "is not a prime number!")
        return
main()

Większość poprzednich odpowiedzi jest poprawnych, ale tutaj jest jeszcze jeden sposób sprawdzenia, czy liczba jest liczbą pierwszą. Odświeżając, liczby pierwsze są liczbą całkowitą większą niż 1, której jedynymi czynnikami są 1 i siebie. ( Źródło )

Rozwiązanie:

Zwykle możesz zbudować pętlę i rozpocząć testowanie swojego numeru, aby sprawdzić, czy jest podzielny przez 1, 2, 3 ... aż do liczby, którą testujesz ... itd., Ale aby skrócić czas sprawdzania, możesz podzielić liczbę przez połowa wartości Twojej liczby, ponieważ liczba nie może być dokładnie podzielna przez cokolwiek powyżej połowy jej wartości. Na przykład, jeśli chcesz zobaczyć, że 100 to liczba pierwsza, możesz zapętlić do 50.

Rzeczywisty kod :

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")  

Możemy użyć strumieni java, aby zaimplementować to w O (sqrt (n)); Weź pod uwagę, że noneMatch jest metodą shortCircuiting, która zatrzymuje operację, gdy uzna ją za niepotrzebną do określenia wyniku:

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");

Za pomocą strumieni Java-8 i lambd można to zaimplementować w zaledwie kilku wierszach:

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

Wydajność powinna być bliska O (sqrt (N)) . Może ktoś uzna to za przydatne.

Oto moja odpowiedź na to pytanie:

def isprime(num):
    return num <= 3 or (num + 1) % 6 == 0 or (num - 1) % 6 == 0

Funkcja zwróci wartość True, jeśli którakolwiek z poniższych właściwości ma wartość True. Te właściwości matematycznie definiują, czym jest liczba pierwsza.

1. Liczba jest mniejsza lub równa 3
2. Liczba + 1 jest podzielna przez 6
3. Liczba - 1 jest podzielna przez 6

Kiedy muszę zrobić szybką weryfikację, piszę ten prosty kod w oparciu o podstawowy podział na liczby mniejsze niż pierwiastek kwadratowy z wejścia.

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
        return True != n==1

isprime(22783)

• Ostatnim True != n==1jest uniknięcie sprawy n=1.