Поиск позиции основного номера заканчивается в слишком большом масштабе, что делать?

Question

def isprime(number):
    counter = 0
    for n in range(1,number+1):
        if number % n == 0:
            counter += 1

    if counter == 2:
        return True

Это функция для проверки, является ли число простым.

my_list = []
n1 = 1
while len(my_list) <= 10000:
    n1 += 1
    if isprime(n1) is True:
        my_list.append(n1)


print(my_list[-1])

Итак, это мой код, он работает совершенно нормально, но не оптимизирован вообще, и я хотелузнать снизу вверх, как сделать такую ​​функцию быстрее, чтобы мой компьютер мог выполнять вычисления.Я пытался найти простое число 10001.(началось с нуля, так что причина <= 10000) </p>

Answer 1

Для чисел, размер которых нужно решить Project Euler # 7 , достаточно определить первичность путем пробного деления.Вот простая проверка простоты с использованием колеса 2,3,5, что примерно в два раза быстрее, чем наивная проверка простоты, опубликованная Яковом Даном:

def isPrime(n): # 2,3,5-wheel
    ws = [1,2,2,4,2,4,2,4,6,2,6]
    w, f = 0, 2
    while f * f <= n:
        if n % f == 0:
            return False
        f = f + ws[w]
        w = w + 1
        if w == 11: w = 3
    return True

Для больших чисел лучше использоватьпроверка первичности Миллера-Рабина:

def isPrime(n, k=5): # miller-rabin
    from random import randint
    if n < 2: return False
    for p in [2,3,5,7,11,13,17,19,23,29]:
        if n % p == 0: return n == p
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d/2
    for i in range(k):
        x = pow(randint(2, n-1), d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return False
            if x == n-1: break
        else: return False
    return True

Любой из этих методов будет намного медленнее, чем сито Эратосфена, изобретенное более двух тысяч лет назад греческим математиком:

def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps

Чтобы решить Project Euler # 7, вызовите сито с n = 120000 и отбросьте лишние простые числа.Вам будет удобнее использовать сито в форме генератора:

def primegen(start=0): # stackoverflow.com/a/20660551
    if start <= 2: yield 2    # prime (!) the pump
    if start <= 3: yield 3    # prime (!) the pump
    ps = primegen()           # sieving primes
    p = next(ps) and next(ps) # first sieving prime
    q = p * p; D = {}         # initialization
    def add(m, s):            # insert multiple/stride
        while m in D: m += s  #   find unused multiple
        D[m] = s              #   save multiple/stride
    while q <= start:         # initialize multiples
        x = (start // p) * p  #   first multiple of p
        if x < start: x += p  #   must be >= start
        if x % 2 == 0: x += p #   ... and must be odd
        add(x, p+p)           #   insert in sieve
        p = next(ps)          #   next sieving prime
        q = p * p             #   ... and its square
    c = max(start-2, 3)       # first prime candidate
    if c % 2 == 0: c += 1     # candidate must be odd
    while True:               # infinite list
        c += 2                #   next odd candidate
        if c in D:            #   c is composite
            s = D.pop(c)      #     fetch stride
            add(c+s, s)       #     add next multiple
        elif c < q: yield c   #   c is prime; yield it
        else: # (c == q)      #   add p to sieve
            add(c+p+p, p+p)   #     insert in sieve
            p = next(ps)      #     next sieving prime
            q = p * p         #     ... and its square

Все эти вещи я обсуждаю на моем блоге .

Answer 2

Быстрые тесты на простоту являются огромным предметом.

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

Итак, попробуйте это:

def is_prime(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
    for d in range(5, int(n**0.5)+1,2):
        if n % d == 0
           return False

    return True