Ответ 1

Существует много способов выполнить тест на первичность.

На самом деле нет структуры данных для запроса. Если у вас есть много номеров для тестирования, вероятно, вы должны запустить вероятностный тест, поскольку они быстрее, а затем выполните его с помощью детерминированный тест, чтобы убедиться, что число является простым.

Вы должны знать, что математика за самыми быстрыми алгоритмами не для слабонервных.

Ответ 2

Самый быстрый алгоритм общего простого тестирования - AKS. Статья в Википедии описывает его подробно и ссылки на оригинальную бумагу.

Если вы хотите найти большие числа, посмотрите на простые числа, которые имеют специальные формы, такие как простые Мерсенны.

Алгоритм, который я обычно реализую (легко понять и кодировать), выглядит следующим образом (в 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

Это вариант классического алгоритма O(sqrt(N)). Он использует тот факт, что простой (кроме 2 и 3) имеет вид 6k - 1 или 6k + 1 и выглядит только на делителях этой формы.

Иногда, если мне действительно нужна скорость, и диапазон ограничен, я реализую псевдопробный тест, основанный на теореме Ферма. Если мне действительно нужна дополнительная скорость (т.е. Вообще избегайте алгоритма O (sqrt (N)), я предварительно компрометирую ложные срабатывания (см. Номера Carmichael) и выполняю двоичный поиск. Это, безусловно, самый быстрый тест, который я когда-либо реализовал, единственным недостатком является то, что диапазон ограничен.

Ответ 3

Лучший метод, на мой взгляд, - использовать то, что было раньше.

Есть списки первых N простых чисел в Интернете с N, простирающимися как минимум пятьдесят миллионов. Загрузите файлы и используйте их, вероятно, намного быстрее, чем любой другой метод, который вы придумаете.

Если вам нужен настоящий алгоритм для создания собственных простых чисел, в Википедии есть всевозможные хорошие вещи на простых словах здесь, включая ссылки на различные методы для этого и первичное тестирование здесь, как основанные на вероятности, так и методы быстрого детерминирования.

Должны быть предприняты согласованные усилия, чтобы найти первые миллиарды (или даже больше) простых чисел и опубликовать их в сети где-нибудь, чтобы люди могли перестать выполнять эту же работу снова и снова и снова и...: -)

Ответ 4

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;
}
this is just c++ implementation of above  AKS algorithm

https://en.wikipedia.org/wiki/AKS_primality_test

Ответ 5

Согласно wikipedia, Сито Эратосфена сложность O(n * (log n) * (log log n)) и требует O(n) памяти - так что это очень хорошее место для начала, если вы не тестируете особенно большие числа.

Ответ 6

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

Пояснение: Простое число - это число, которое делится только на себя и 1. Пример: 2,3,5,7...

1) если a <2: если "a" меньше 2, это не простое число.

2) elif a! = 2 и a% 2 == 0: если "a" делится на 2, то это определенно не простое число. Но если a = 2, мы не хотим оценивать это, поскольку это простое число. Отсюда условие а! = 2

3) вернуть все (% я для я в диапазоне (3, int (a 0,5) +1)): ** Сначала посмотрите, что команда all() делает в python. Начиная с 3 мы делим "а" до его квадратного корня (а ** 0,5). Если "а" делится, вывод будет ложным. Почему квадратный корень? Пусть скажет а = 16. Квадратный корень из 16 = 4. Нам не нужно оценивать до 15. Нам нужно только проверить до 4, чтобы сказать, что это не простое число.

Дополнительно: цикл для нахождения всех простых чисел в диапазоне.

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

Ответ 7

Я сравнил эффективность самых популярных предложений, чтобы определить, является ли число простым. Я использовал python 3.6 на ubuntu 17.10; Я проверил с номерами до 100.000 (вы можете проверить с большими числами, используя мой код ниже).

На этом первом графике сравниваются функции (которые объясняются ниже в моем ответе), показывая, что последние функции растут не так быстро, как первая при увеличении чисел.

И на втором графике мы видим, что в случае простых чисел время неуклонно растет, но не простые числа растут не так быстро во времени (поскольку большинство из них можно устранить на ранней стадии).

Вот функции, которые я использовал:

1. этот ответ и этот ответ предложили конструкцию с использованием all():

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

2. Этот ответ использовал какой-то цикл 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. Этот ответ включал версию с циклом for:

   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. И я смешал несколько идей из других ответов в новый:

   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
   

Вот мой скрипт для сравнения вариантов:

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

Запуск функции compare_functions(n=10**5) (числа до 100.000) Я получаю такой вывод:

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

Затем, запустив функцию compare_functions(n=10**6) (числа до 1.000.000), я получаю следующий вывод:

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

Для построения результатов я использовал следующий скрипт:

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

Ответ 8

Можно использовать sympy.

import sympy

sympy.ntheory.primetest.isprime(33393939393929292929292911111111)

True

Из симплексных документов. Первый шаг - поиск тривиальных факторов, которые, если их обнаруживают, позволяют быстро вернуться. Затем, если сито достаточно большое, используйте поиск по бисекции на сите. Для небольших чисел набор детерминированных тестов Миллера-Рабина выполняется с базами, которые, как известно, не имеют контрпримеров в своем диапазоне. Наконец, если число больше 2 ^ 64, выполняется сильный тест BPSW. Хотя это вероятный первичный тест, и мы считаем, что существуют контрпримеры, нет известных контрпримеров

Ответ 9

Для больших чисел вы не можете просто наивно проверить, делится ли число кандидатов N на одно из чисел, меньших, чем sqrt (N). Доступны гораздо более масштабируемые тесты, такие как тест первичности Миллера-Рабина. Ниже у вас есть реализация в Python:

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 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 little theorem, hence not a prime.
                return False
    # No contradiction found, hence x must be a prime.
    return True

Вы можете использовать его, чтобы найти огромные простые числа:

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

# 10000000000000000000000000000000000000000000000000000000000000000000000000133 is a prime!

Если вы тестируете случайные целые числа, возможно, вы хотите сначала проверить, делится ли число кандидатов на любое из простых чисел, меньших, например, 1000, прежде чем позвонить Миллеру-Рабину. Это поможет вам отфильтровать очевидные не простые числа, такие как 10444344345.

Ответ 10

Python 3:

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

Ответ 11

Слишком поздно для вечеринки, но надеюсь, что это поможет. Это актуально, если вы ищете большие простые числа:

Чтобы проверить большие нечетные числа, вам нужно использовать тест Fermat-test и/или Miller-Rabin.

Эти тесты используют модульное возведение в степень, которое довольно дорогое, для экспоненции n бит вам нужно как минимум n большого умножения int и n большого int divison. Это означает, что сложность модульного возведения в степень - O (n³).

Поэтому, прежде чем использовать большие пушки, вам нужно сделать несколько пробных подразделений. Но не делайте это наивно, есть способ быстро их сделать. Сначала умножьте столько простых чисел вместе, сколько вписывается в слова, которые вы используете для больших целых чисел. Если вы используете 32-битные слова, умножьте 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 3234846615 и вычислите наибольший общий делитель с номером, который вы проверите, используя алгоритм Евклида. После первого шага число уменьшается ниже размера слова и продолжает алгоритм без выполнения полных больших целых делений. Если GCD! = 1, это означает, что один из простых чисел, которые вы умножили, делит число, поэтому у вас есть доказательство, что оно не простое. Затем продолжайте с 31 * 37 * 41 * 43 * 47 = 95041567 и так далее.

После того, как вы проверили несколько сотен (или тысяч) простых чисел таким образом, вы можете выполнить 40 раундов теста Миллера-Рабина, чтобы подтвердить, что число является простым, после 40 раундов вы можете быть уверены, что число является простым, есть только вероятность 2 ^ -80 это не (скорее, ваши аппаратные сбои...).

Ответ 12

У меня есть основная функция, которая работает до (2 ^ 61) -1 Здесь:

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

Объяснение:

Функция all() может быть переопределена следующим образом:

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

Функция all() просто проходит через ряд bools/numbers и возвращает False если она видит 0 или False.

Функция sqrt() просто выполняет квадратный корень из числа.

Например:

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

Часть num % x возвращает оставшуюся часть num/x.

Наконец, range(2, int(sqrt(num))) означает, что он создаст список, начинающийся с 2 и заканчивающийся на int(sqrt(num)+1)

Для получения дополнительной информации о диапазоне, посмотрите на этом сайте !

Параметр num > 1 просто проверяет, превышает ли переменная num более 1, потому что 1 и 0 не считаются простыми числами.

Надеюсь, это помогло :)

Ответ 13

В Python:

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

Более прямое преобразование из математического формализма в Python будет использовать все (n% p! = 0...), но это требует строгой оценки всех значений p. Не любая версия может заканчиваться раньше, если найдено Истинное значение.

Ответ 14

лучший алгоритм для числа Primes javascript

 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
    }

Ответ 15

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

Ответ 16

Аналогичная идея с алгоритмом 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;
}

Ответ 17

Чтобы узнать, является ли число или числа в диапазоне/основными.

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

Ответ 18

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

Ответ 19

Вы могли бы попробовать что-то вроде этого.

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

Ответ 20

Большинство предыдущих ответов верны, но вот еще один способ проверить, является ли число простым числом. В качестве повторного обновления простые числа целые числа больше 1, единственными факторами которых являются 1 и сам (источник)

Решение:

Как правило, вы можете построить цикл и начать тестирование своего номера, чтобы узнать, делится ли он на 1,2,3... до числа, которое вы тестируете... и т.д., Но чтобы сократить время проверки, вы можете разделить свой номер на половину значения вашего номера, потому что число не может быть точно делит на что-либо выше половины его значения. Например, если вы хотите видеть 100, это простое число, которое вы можете прокрутить до 50.

Фактический код:

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 a prime number !!")
else:
    print("it not a prime")  

Ответ 21

Мы можем использовать потоки java для реализации этого в O (sqrt (n)); Учтите, что noneMatch - это метод shortCircuiting, который останавливает операцию, если для определения результата нет необходимости:

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

Ответ 22

С помощью потоков и лямбд Java-8 это может быть реализовано следующим образом:

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

Производительность должна быть близка к O (sqrt (N)). Может быть, кто-то найдет это полезным.

Ответ 23

Вот мой взгляд на ответ:

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

Функция вернет True, если какое-либо из приведенных ниже свойств имеет значение True. Эти свойства математически определяют, что такое простое число.

1. Число меньше или равно 3
2. Число + 1 делится на 6
3. Число - 1 делится на 6

Ответ 24

Простое число - это любое число, которое делится только на 1 и на себя. Все остальные числа называются составными.

Самый простой способ найти простое число - проверить, является ли введенное число составным числом:

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

Программа должна делить значение number на все целые числа от 1 и до его значения. Если это число можно разделить поровну не только на одно, а на самом деле, это составное число.

Начальное значение переменной i должно быть 2, потому что как простые, так и составные числа могут быть равномерно разделены на 1.

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

Тогда i меньше, чем number по той же причине. Простые и составные числа могут быть равномерно разделены между собой. Поэтому нет причин проверять это.

Затем мы проверяем, можно ли разделить переменную равномерно, используя оператор остатка.

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

Если остаток равен нулю, это означает, что number можно разделить равномерно, следовательно, составное число и возвращение false.

Если введенный номер не удовлетворяет условию, это означает, что это простое число, и функция возвращает true.

Ответ 25

Малая память? Это не самый маленький, но это шаг в правильном направлении.

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

Конечно, вы должны указать определение CheckPrimality.

Ответ 26

Я думаю, что одним из самых быстрых является мой метод, который я сделал.

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

Ответ 27

Вы можете попробовать этот код:

def isprime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True

Чтобы использовать его, просто введите isprime(NUMBER)

Используя этот код, вы можете спросить пользователя о номере и проверить, является ли он основным:

def isprime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True
while True:
    number = input('Please Enter A Number: ')
    if isprime(int(number)):
        print('The Number You Entered Is A Prime Number', end='\n\n')
    else:
        print('The Number You Entered Is Not A Prime Number', end='\n\n')

Ответ 28

public class PrimeNumberOrNot {

    public static void main(String[] args) {
        System.out.println(isPrimeOrNot(12345673));
    }

    public static String isPrimeOrNot(int num) {
        if (num < 0) {
            return "not valid";
        }
        if (num == 0 || num == 1) {
            return "not prime";
        }
        if (num == 2 || num == 3) {
            return "prime number";
        }
        if ((num * num - 1) % 24 == 0) {
            return "prime";
        } else {
            return "not prime";
        }
    }
}

Ответ 29

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

Ответ 30

Первое правило простого числа: если разделить на 2, это будет целое число или целое число Нет, это не простое число.

Самый быстрый способ узнать, используя любой компьютерный язык - это сопоставление типов с использованием строк, а не математики. Сопоставьте ТОЧКУ в струнном поплавке.

• Разделите это на 2 ,, n = n/2
• Преобразовать это в строку ,, n = string (n)
• если "." в п: {printf "Да, я премьер!"
  } }