Hướng dẫn prime number using filter in python - số nguyên tố sử dụng bộ lọc trong python

Tôi có một danh sách chứa đầy các số ngẫu nhiên và tôi muốn trả lại các số nguyên tố từ danh sách này. Vì vậy, tôi đã tạo các chức năng này:

def is_prime[number]:
    for i in range[2, int[sqrt[number]] + 1]:
        if number % i == 0:
            return False

    return number > 1

Và

def filter_primes[general_list]:
    return set[filter[is_prime, general_list]]

Nhưng tôi muốn cải thiện hiệu suất, vậy làm thế nào tôi có thể đạt được điều này?

Đã hỏi ngày 2 tháng 7 năm 2017 lúc 14:14Jul 2, 2017 at 14:14

flpnflpnflpn

1.7682 Huy hiệu vàng17 Huy hiệu bạc29 Huy hiệu đồng2 gold badges17 silver badges29 bronze badges

8

Sây eratosthenes, mất khoảng 0,17 giây cho các số nguyên tố dưới 10 triệu trên Pypy 3,5 trên thiết bị của tôi:

from array import array
from math import isqrt

def primes[upper]:
    numbers = array['B', [1]] * [upper + 1]

    for i in range[2, isqrt[upper] + 1]:
        if numbers[i]:
            low_multiple = i * i
            numbers[low_multiple:upper + 1:i] = array['B', [0]] * [[upper - low_multiple] // i + 1]

    return {i for i, x in enumerate[numbers] if i >= 2 and x}

và chức năng bộ lọc:

filter_primes = primes[10_000_000].intersection

Đã trả lời ngày 2 tháng 7 năm 2017 lúc 15:25Jul 2, 2017 at 15:25

Ry- ♦ ry-♦Ry-

213K54 Huy hiệu vàng446 Huy hiệu bạc459 Huy hiệu Đồng54 gold badges446 silver badges459 bronze badges

3

3 vòng của bài kiểm tra Miller-Rabin [//en.wikipedia.org/wiki/Miller%2Drabin_Primality_Test] bằng cách sử dụng các cơ sở 2, 7 và 61, được biết là phát hiện chính xác tất cả các số nguyên tố

Điều này là nhiều, nhanh hơn nhiều so với phân chia thử nghiệm hoặc sàng nếu các con số có thể lớn.

Nếu các số không thể lớn [tức là,