Поиск n-го числа для больших чисел n [duplicate]

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

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

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

И, (n ** 0.5) -> Это даст нам квадрат root "из '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 начинает уменьшаться ... Итак, в конечном счете мы проверяем делимость с числами меньше квадратного корня.

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

Объяснение для «магического регулярного выражения» можно найти здесь

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

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

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

from math import factorial

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

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

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, если нет.

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

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

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

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.

У меня есть новое решение, которое, я думаю, может быть быстрее, чем любая из упомянутых функций в 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 == square root (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

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

Вот мой

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

( https://www.youtube.com/watch?v=Vxw1b8f_yts&t=3384s ) Avinash Jain

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

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

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

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

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

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

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

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

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

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(x):  
    if x < 2:  
        return False  
    for n in range(2, (x) - 1):  
        if x % n == 0:  
            return False  
    return True

Это мой способ 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

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

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

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

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, где будут искать простые числа.

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