IsPrime Функция для языка Python

Ответ 1

Во многих тестах primality, плавающих вокруг Интернета, рассмотрите следующий простой тест:

def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  f = 5
  while f <= r:
    print '\t',f
    if n%f == 0: return False
    if n%(f+2) == 0: return False
    f +=6
  return True    

Рассмотрим простое число 5003:

print is_prime(5003)

Печать

 5
 11
 17
 23
 29
 35
 41
 47
 53
 59
 65
True

Линия r = int(n**0.5) оценивается до 70 (квадратный корень из 5003 равен 70.7318881411, а int() обрезает это значение)

Из-за первых нескольких тестов и тестов в середине цикла цикл нужно только оценивать каждые 6-е число.

Рассмотрим следующее нечетное число (поскольку все четные числа, отличные от 2, не являются первыми) из 5005, то же самое печатает:

 5
False

Предел - это квадратный корень, так как x*y == y*x Функция должна пройти только 1 цикл, чтобы найти, что 5005 делится на 5 и поэтому не является простым. Поскольку 5 X 1001 == 1001 X 5 (и оба они 5005), нам не нужно пройти весь путь до 1001 в цикле, чтобы знать, что мы знаем в 5!

Теперь посмотрим на алгоритм, который у вас есть:

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

    return True

Есть две проблемы:

• Он не проверяет, если n меньше 2, и нет простых чисел меньше 2;
• Он проверяет каждое число между 2 и n ** 0.5, включая все четные и все нечетные числа. Поскольку каждое число, большее 2, которое делится на 2, не является простым, мы можем немного ускорить его, только проверяя нечетные числа больше 2.

Итак:

def isPrime2(n):
    if n==2 or n==3: return True
    if n%2==0 or n<2: return False
    for i in range(3,int(n**0.5)+1,2):   # only odd numbers
        if n%i==0:
            return False    

    return True

OK - это ускоряет его примерно на 30% (я сравнивал его...)

Алгоритм, который я использовал is_prime, примерно в 2 раза быстрее, так как только каждое 6-е целое циклически проходит цикл. (Еще раз, я сравнивал его.)

Боковое примечание: x ** 0.5 - это квадратный корень:

>>> import math
>>> math.sqrt(100)==100**0.5
True

Замечание 2: приматов - интересная проблема в информатике.

Ответ 2

С n**.5 вы не занимаете квадрат n, а получаете квадратный корень.

Рассмотрим число 20; целые коэффициенты равны 1, 2, 4, 5, 10 и 20. Когда вы разделите 20 на 2 и получите 10, вы знаете, что он также делится на 10, без необходимости проверять. Когда вы разделите его на 4 и получите 5, вы знаете, что он делится на 4 и 5, без необходимости проверять 5.

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

Кроме того, причина 1 не является простым числом, так как простые числа определяются как имеющие 2 фактора, 1 и себя. то есть 2 1 * 2, 3 равно 1 * 3, 5 равно 1 * 5. Но 1 (1 * 1) имеет только один фактор. Поэтому оно не соответствует этому определению.

Ответ 3

isPrime(Number):
    return 2 in [Number,2**Number%Number]

Математическая операция всегда возвращает 2, если число является простым, а не 2. Но если 2 - заданное число, оно добавляется к списку, в котором мы ищем.

2^5=32    32%5=2
2^7=128   128%7=2
2^11=2048 2048%11=2

и т.д.

isPrime() возвращает True, если Number является Prime, а False, если нет.

Ответ 4

Операции с плавающей запятой не выполняются ниже. Это быстрее и будет терпеть более высокие аргументы. Причина, по которой вы должны идти только в квадратный корень, состоит в том, что если число имеет коэффициент больше, чем его квадратный корень, он также имеет меньший множитель.

def is_prime(n):
    """"pre-condition: n is a nonnegative integer
    post-condition: return True if n is prime and False otherwise."""
    if n < 2: 
         return False;
    if n % 2 == 0:             
         return n == 2  # return False
    k = 3
    while k*k <= n:
         if n % k == 0:
             return False
         k += 2
    return True

Ответ 5

Поиск квадратного корня из числа для эффективности. например. если я пытаюсь найти коэффициенты 36, то наибольшее число, которое может быть умножено на себя на форму 36, равно 6. 7 * 7 = 49.

поэтому каждый коэффициент 36 должен умножаться на 6 или меньшее число.

Ответ 6

def is_prime(x):
    if x < 2:
        return False
    elif x == 2:
        return True  
    for n in range(2, x):
        if x % n ==0:
            return False
    return True

Ответ 7

Этот метод будет медленнее, чем рекурсивные и перечислительные методы, но использует теорему Вильсона и представляет собой одну строку:

from math import factorial

def is_prime(x):
    return factorial(x - 1)  % x == x - 1

Ответ 8

def isPrime(num,div=2):
    if(num==div):
        return True
    elif(num % div == 0):
        return False
    else:
        return isPrime(num,div+1)

==============================================
РЕДАКТИРОВАНИЕ

def is_prime(num, div = 2):
    if num == div: return True
    elif num % div == 0: return False
    elif num == 1: return False
    else: return is_prime(num, div + 1)

Ответ 9

isPrime=lambda x: all(x % i != 0 for i in range(int(x**0.5)+1)[2:])

и вот как его использовать

isPrime(2) == False
isPrime(5) == True
isPrime(7) == True

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

filter(isPrime, range(4000)[2:])[:5]
=> [2, 3, 5, 7, 11]

Обратите внимание, что в этом случае 5 обозначает число простых чисел, которое можно найти, и 4000 max диапазона, где будут искать простые числа.

Ответ 10

Каждый написанный вами код должен быть эффективным. Для начинающего, как и вам, самый простой способ - проверить делимость числа 'n' от 2 до (n-1). Это занимает много времени, когда вы считаете очень большие цифры. Метод с квадратным корнем помогает быстрее сделать код за счет меньшего количества сравнений. Читайте о сложностях в разработке и анализе алгоритмов.

Ответ 11

Я не знаю, опаздываю ли я, но я оставлю это здесь, чтобы помочь кому-то в будущем.

Мы используем квадратный корень из (n) i.e int (n ** 0.5), чтобы уменьшить диапазон чисел, которые ваша программа будет вынуждена вычислять.

Например, мы можем выполнить пробное деление, чтобы проверить простоту 100. Посмотрим на все делители 100:

2, 4, 5, 10, 20, 25, 50 Здесь мы видим, что наибольший коэффициент равен 100/2 = 50. Это справедливо для всех n: все делители меньше или равны n/2. Если мы более подробно рассмотрим дивизоров, мы увидим, что некоторые из них являются избыточными. Если мы будем писать список по-разному:

100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2 избыточность становится очевидной. Как только мы достигнем 10, что составляет √100, делители просто поворачиваются и повторяются. Поэтому мы можем дополнительно исключить тестовые дивизоры, превышающие √n.

Возьмите еще одно число, например 16.

Его делители равны 2,4,8

16 = 2 * 8, 4 * 4, 8 * 2.

Вы можете заметить, что после достижения 4, который является квадратным корнем из 16, мы повторили 8 * 2, которые мы уже сделали как 2 * 8. Этот шаблон справедлив для всех чисел.

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

Итак, мы преобразуем квадратный корень в int, потому что нам не нужен диапазон с плавающими числами.

Прочтите тест primality на wikipedia для получения дополнительной информации.

Ответ 12

Это мой метод:

import math

def isPrime(n):
    'Returns True if n is prime, False if n is not prime. Will not work if n is 0 or 1'

    # Make sure n is a positive integer
    n = abs(int(n))

    # Case 1: the number is 2 (prime)
    if n == 2: return True

    # Case 2: the number is even (not prime)
    if n % 2 == 0: return False

    # Case 3: the number is odd (could be prime or not)

    # Check odd numbers less than the square root for possible factors 
    r = math.sqrt(n)
    x = 3 
    while x <= r:
        if n % x == 0: return False  # A factor was found, so number is not prime
        x += 2 # Increment to the next odd number

    # No factors found, so number is prime  
    return True 

Чтобы ответить на исходный вопрос, n ** 0,5 совпадает с квадратом корня n. Вы можете остановить проверку факторов после этого числа, потому что составное число всегда будет иметь коэффициент меньше или равен его квадратному корню. Это быстрее, чем просто проверка всех факторов между 2 и n для каждого n, поскольку мы проверяем меньшее количество чисел, что экономит больше времени с ростом n.

Ответ 13

def is_prime(x):  
    if x < 2:  
        return False  
    for n in range(2, (x) - 1):  
        if x % n == 0:  
            return False  
    return True

Ответ 14

Реализовано псевдокод (https://en.wikipedia.org/wiki/Primality_test) в python, надеюсь, что эта помощь.

# original pseudocode https://en.wikipedia.org/wiki/Primality_test
def isPrime(n):
    # Corner Cases
    if (n<= 1): return False
    elif (n<= 3): return True
    elif (n%2 == 0 or n%3 == 0): return False

    i = 5
    while i*i<=n:
        if (n%i==0 or n%(i+2)==0): return False
        i += 6

    return True;

%timeit isPrime(800)

Ответ 15

int(n**0.5) - это значение пола sqrt (n), которое вы путаете с мощностью 2 n (n**2). Если n не является простым, то должно быть два числа 1 < i <= j < n такие, что: i * j = n.

Теперь, поскольку sqrt(n) * sqrt(n) = n, предполагая, что один из i,j больше (или равен) sqrt(n) - это означает, что другой должен быть меньше (или равен) sqrt(n).

Так как это так, это достаточно хорошо, чтобы перебирать целые числа в диапазоне [2, sqrt(n)]. И это именно то, что делает код, который был отправлен.

Если вы хотите выйти в качестве реального смартфона, используйте следующую однострочную функцию:

import re
def is_prime(n):    
    return not re.match(r'^1?$|^(11+?)\1+$',n*'1')

Объяснение "волшебного регулярного выражения" можно найти здесь

Ответ 16

def fun(N):#prime test
if N>1 :
    for _ in xrange(5):
        Num=randint(1,N-1)
        if pow(Num,N-1,N)!=1:
            return False
    return True
return False

Истинно, если число является простым, иначе false

Ответ 17

Это мой способ np:

def is_prime(x):
    if x < 4:
        return True
    if all([(x > 2), (x % 2 == 0)]):
        return False
    else:
        return np.array([*map(lambda y: ((x % y) == 0).sum(), np.arange(1, x + 1))]).sum() == 2

Здесь производительность:

%timeit is_prime(2)
%timeit is_prime(int(1e3))
%timeit is_prime(5003)

10000 loops, best of 3: 31.1 µs per loop
10000 loops, best of 3: 33 µs per loop
10 loops, best of 3: 74.2 ms per loop

Ответ 18

def is_prime(n):
    n=abs(n)
    if n<2:    #Numbers less than 2 are not prime numbers
        return "False"
    elif n==2: #2 is a prime number
        return "True"
    else:
        for i in range(2,n): # Highlights range numbers that can't be  a factor of prime number n. 
            if n%i==0:
                return "False" #if any of these numbers are factors of n, n is not a prime number
    return "True" # This is to affirm that n is indeed a prime number after passing all three tests

Ответ 19

Это было упражнение в codecademy и вот как я прошел его ниже...

def is_prime(x):  

    # If number(x) is evenly divided by following dividers then number(x) is not prime

    divider = [2, 3, 5, 7]

    # An empty list to be able to check whether number(x) is evenly divided:

    remainder = []

    # exceptions for numbers 1,2,3,5,7:
    if x < 2:
        return False
    if x in divider:
        return True
    else:
        for nums in divider:
            remainder.append(x % nums)
        if 0 in remainder:
            return False
        else:
            return True

Ответ 20

def is_prime(n):
if (n==2 or n==3): return True
if(n<=1 or n%2==0 or n%3==0 ): return False
for i in range(6,int((n**0.5)) + 2,6):
    if(n%(i-1)==0 or n%(i+1)==0):
        return False
return True

Ответ 21

Довольно просто!

def prime(x):
  if x == 1:
    return False
  else:
    for a in range(2,x):
      if x % a == 0:
        return False
  return True

Ответ 22

Число 1 - частный случай, который не считается ни простым, ни композиционным. Для получения дополнительной информации посетите: http://mathworld.wolfram.com/PrimeNumber.html

А, (n ** 0,5) → Это даст нам " квадратный корень" из "n". Поскольку он "n поднят до мощности 0,5 или 1/2"

И ПОЧЕМУ мы это делаем, Возьмем, например, номер 400: Мы можем представить его в виде a * b

1*400 = 400
2*200 = 400
4*100 = 400
5*80 = 400
8*50 = 400
10*40 = 400
16*25 = 400
20*20 = 400
25*16 = 400
40*10 = 400
50*8 = 400
80*5 = 400
100*4 = 400
200*2 = 400
400*1 = 400

Квадратный корень 400 составляет 20: и мы можем видеть, что нам нужно всего лишь проверить делимость до 20, потому что, поскольку 'a' достигает 20 'b', начинает уменьшаться... Итак, в конечном счете мы проверяем делимость с числами меньше квадратного корня.

Ответ 23

У меня есть новое решение, которое, я думаю, может быть быстрее любого из упомянутых Функция в Python

Это основано на идее, что: N/D = R для любого произвольного числа N наименьшее возможное число для деления N (если не простое) равно D = 2, а соответствующий результат R равен (N/2) (самый высокий).

По мере того как D больше, результат R становится меньше ex: делят на D = 3 результаты R = (N/3) поэтому, когда мы проверяем, является ли N делимым на D, мы также проверяем, делится ли он на R

так как D больше, а R меньше, чем (D == R == квадратный корень (N))

тогда нам нужно только проверить числа от 2 до sqrt (N) еще один совет, чтобы сэкономить время, нам нужно только проверить нечетные числа, так как он делится на любое четное число, он также будет делиться на 2.

поэтому последовательность будет 3,5,7,9,......, sqrt (N).

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

Ответ 24

(https://www.youtube.com/watch?v=Vxw1b8f_yts&t=3384s) Авинаш Джайн

for i in range(2,5003):
    j = 2
    c = 0
    while j < i:
        if i % j == 0:
            c = 1
            j = j + 1
        else:
            j = j + 1
    if c == 0:
        print(str(i) + ' is a prime number')
    else:
        c = 0

Ответ 25

Вот мой

import math

def is_prime(num):

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

Ответ 26

def is_prime(x):  
    if x<2:  
        return False  
    elif x == 2:  
        return True  
    else:  
        for n in range(2, x):  
            if x%n==0:  
                return False  
        return True

Ответ 27

Srsly guys... Почему так много строк кода для простого метода вроде этого? Здесь мое решение:

def isPrime(a):
    div = a - 1
    res = True
    while(div > 1):
        if a % div == 0:
            res = False
        div = div - 1
    return res