Python tìm số nguyên tố trong dãy

Đây là phiên bản đơn giản và trực quan để kiểm tra xem nó có phải là số nguyên tố trong hàm RECURSIVE hay không. . ) (Tôi đã làm bài tập về nhà cho một lớp MIT) Trong python, nó chạy rất nhanh cho đến năm 1900. NẾU bạn thử hơn 1900, bạn sẽ gặp một lỗi thú vị. ) (Bạn có muốn kiểm tra xem máy tính của bạn có thể quản lý bao nhiêu số không?)

def is_prime(n, div=2):

    if div> n/2.0: return True

    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)

#The program:
until = 1000
for i in range(until):
    if is_prime(i):
        print i

Tất nhiên rồi. nếu bạn thích các hàm đệ quy, mã nhỏ này có thể được nâng cấp bằng từ điển để tăng hiệu suất của nó một cách nghiêm túc và tránh lỗi buồn cười đó. Đây là bản nâng cấp Cấp 1 đơn giản với tích hợp BỘ NHỚ

import datetime
def is_prime(n, div=2):
    global primelist
    if div> n/2.0: return True
    if div < primelist[0]:
        div = primelist[0]
        for x in primelist:
            if x ==0 or x==1: continue
            if n % x == 0:
                return False
    if n% div == 0:
        return False
    else:
        div+=1
        return is_prime(n,div)


now = datetime.datetime.now()
print 'time and date:',now
until = 100000
primelist=[]
for i in range(until):
    if is_prime(i):
        primelist.insert(0,i)
print "There are", len(primelist),"prime numbers, until", until
print primelist[0:100], "..."

finish = datetime.datetime.now()
print "It took your computer", finish - now , " to calculate it"

Đây là kết quả, nơi tôi đã in 100 số nguyên tố cuối cùng được tìm thấy

thời gian và ngày tháng. 2013-10-15 13. 32. 11. 674448

Có 9594 số nguyên tố, đến 100000

[99991, 99989, 99971, 99961, 99929, 99923, 99907, 99901, 99881, 99877, 99871, 99859, 99839, 99833, 99829, 99823, 99817, 99809, 99793, 99787, 99767, 99761, 99733, 99721, 99719

Chạy

low, high = 2, 10
primes = [2, 3]

for num in range(low, high + 1):
    flag = 0
    
    if num < 2:
        flag = 1
        
    if num % 2 == 0:
        continue
        
    if num % 3 == 0:
        continue
        
    iter = 2
    while iter < int(pow(num, 0.5)):
        if num % iter == 0:
            flag = 1
            break
        iter += 1
        
    if flag == 0:
        primes.append(num)

print(primes)

Trong hướng dẫn này, bạn sẽ học cách sử dụng Python để tìm số nguyên tố, bằng cách kiểm tra xem một giá trị đơn lẻ có phải là số nguyên tố hay không hoặc tìm tất cả các số nguyên tố trong một dải giá trị. Số nguyên tố là số không có ước nào khác 1 và chính nó. Có thể làm việc với các số nguyên tố là một nhiệm vụ phổ biến trong các công việc như máy tính và an ninh mạng

Đến cuối hướng dẫn này, bạn sẽ học được

• số nguyên tố là gì
• Các cách khác nhau để tìm số nguyên tố trong Python
• Tối ưu hóa các thuật toán của chúng tôi để tìm số nguyên tố trong Python
• Tìm tất cả các số nguyên tố giữa một phạm vi giá trị trong Python

Mục lục

số nguyên tố là gì

Số nguyên tố là số nguyên dương lớn hơn 1 và không có thừa số nào khác ngoài 1 và chính số đó. Ví dụ: số 5 là số nguyên tố, còn số 6 thì không (vì 2 x 3 bằng 6)

Một số số nguyên tố đầu tiên là. 3, 7, 11, 13, v.v.

Tìm số nguyên tố trong Python (Mã được tối ưu hóa)

Hãy xem cách chúng ta có thể sử dụng Python để xác định xem một số có phải là số nguyên tố không. Cách thực hiện ngây thơ và đơn giản nhất là lặp qua phạm vi số từ 2 đến số và xem liệu modulo của số và phạm vi có bằng 0 không. Nếu điều đó xảy ra thì số đó có ước khác 1 và chính số đó và số đó không phải là số nguyên tố

Hãy xem cách chúng ta có thể triển khai mã đầu tiên này

# Writing a Simple Function to Check if a Number is a Prime Number
def is_prime(number):
    if number > 1:
        for num in range(2, number):
            if number % num == 0:
                return False
        return True
    return False

print(is_prime(4))

# Returns: False

Hãy phá vỡ những gì chúng tôi đã làm ở đây

1. Chúng tôi đã định nghĩa một hàm is_prime nhận một đối số duy nhất, một số
2. Nếu số không lớn hơn 1, thì hàm trả về False vì các số nguyên tố cần phải lớn hơn 1
3. Sau đó, nó lặp lại phạm vi từ 2 đến số (nhưng không bao gồm)
4. Nếu modulo của số và phép lặp bằng 0 (có nghĩa là số được chia sạch), thì hàm trả về False
5. Nếu không, hàm trả về True

Chức năng này hoạt động tốt. Tuy nhiên, nó không phải là chức năng hiệu quả nhất. Chúng ta có thể chia số cho 2 vì bất kỳ hợp số nào (một số không phải là số nguyên tố) cũng sẽ có một nửa ước số của nó

Điều này có nghĩa là số lần lặp mà mã của chúng tôi phải hoàn thành đã giảm khoảng một nửa. Hãy xem cách chúng ta có thể viết chức năng này

# Improving our function
def is_prime(number):
    if number > 1:
        for num in range(2, number // 2 + 1):
            if number % num == 0:
                return False
        return True
    return False

print(is_prime(941))

Trong chức năng trên, chúng tôi đã thực hiện cải tiến sau

1. Chúng tôi sử dụng phép chia sàn để chia cho hai và trả về một số nguyên
2. Chúng tôi thêm một để đi đến con số đó

Bây giờ, hãy xem một cải tiến nữa mà chúng ta có thể thực hiện. Chúng tôi thực sự có thể lấy căn bậc hai của số mà chúng tôi đang kiểm tra. Điều này có thể cải thiện đáng kể số lần kiểm tra mà chức năng cần thực hiện

Hãy xem nó trông như thế nào

# The Final Function to Check for Prime Numbers
def is_prime(number):
    if number > 1:
        for num in range(2, int(number**0.5) + 1):
            if number % num == 0:
                return False
        return True
    return False

print(is_prime(2011))

# Returns: True

Trong phần tiếp theo, bạn sẽ học cách tìm tất cả các số nguyên tố trong một dãy số

So sánh hiệu suất của các hàm số nguyên tố

Bây giờ chúng tôi đã phát triển ba chức năng, chúng tôi có thể dễ dàng so sánh hiệu suất của các chức năng này để xem mức tăng hiệu suất mà chúng tôi sẽ nhận được từ chúng

Để kiểm tra những điều này, hãy sử dụng một số nguyên tố lớn, 433.494.437. Vì chúng ta biết số này là số nguyên tố nên hàm sẽ cần chạy qua tất cả các lần lặp

Bảng dưới đây phân tích hiệu suất giữa ba chức năng này

Thực hiện FunctionRuntimeNaive27. 24 giây Tầng 12. 12 giây Căn bậc hai 0. 0013 giâyHiệu suất của các hàm số nguyên tố của chúng tôi

Chúng ta có thể thấy rằng phương pháp căn bậc hai nhanh hơn đáng kể so với các phương pháp khác

Tìm tất cả các số nguyên tố trong dãy số

Một thử thách chung sẽ là tìm tất cả các số nguyên tố nằm giữa hai số khác nhau. Để làm được điều này, chúng ta có thể sử dụng hàm đã tối ưu hóa ở trên và lặp qua một dãy số để trả về tất cả các giá trị là số nguyên tố

Hãy xem cách chúng ta có thể làm điều này cho các giá trị từ 100 đến 300

# Finding All Prime Numbers Between 100 and 300
prime_numbers = []
for num in range(100, 301):
    if is_prime(num):
        prime_numbers.append(num)

print(prime_numbers)

# Returns:
# [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293]

Phần kết luận

Trong hướng dẫn này, bạn đã học cách sử dụng Python để kiểm tra xem một số có phải là số nguyên tố hay không. Trước tiên, bạn học cách triển khai đơn giản, sau đó học cách tối ưu hóa chức năng của mình để giảm đáng kể thời gian chạy của nó. Cuối cùng, bạn đã học cách tìm tất cả các số nguyên tố trong một dãy số bằng chức năng nâng cao này