Tính toán số nguyên tố và phụ thêm vào danh sách

Question

Gần đây tôi đã bắt đầu cố gắng giải quyết các vấn đề về dự án Euler bằng cách sử dụng python và đã gặp phải tình trạng này khi cố tính số nguyên tố và thêm chúng vào danh sách. Tôi đã viết mã sau đây, nhưng tôi bối rối là tại sao nó không xuất ra bất cứ thứ gì khi tôi chạy nó.

import math 

primes = [] 

def isPrime(i): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for i in range(3,int(sqrt(number))+1): 
     if number%i==0: 
      return False 
    return True 

for i in range (1, 9999999): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 
print(primes) 

Answer 1

Hãy thử:

import math 

primes = [] 

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

for i in range (1, 9999999): 
    if isPrime(i) == True: 
     primes.append(i) 

print(primes) 

Answer 2

Hãy thử điều này:

import math 

primes = [] 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for ind in range(3,int(math.sqrt(number))+1): 
     if number%ind==0: 
      return False 
    return True 

for i in range (1, 100): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 

print(primes) 

Để hiển thị nó làm việc, tôi in đầu tiên 100:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 

Answer 3

Sử dụng một danh sách có điều kiện hiểu biết:

primes = [ 
    i for i in range(1, 9999999) 
    if i == 2 
    or i > 2 # Anything less than 2 is not prime. 
    and i % 2 # No evens (except for 2 above) 
    and all(i % n for n in range(3, int(i ** 0.5) + 1))] 

>>> primes[:10] 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

>>> primes[-10:] 
[9999889, 
9999901, 
9999907, 
9999929, 
9999931, 
9999937, 
9999943, 
9999971, 
9999973, 
9999991] 

Answer 4

Cách dễ nhất để thực hiện việc này là sử dụng thứ gọi là Rây. Đây là cách để có được tất cả các số nguyên tố lên đến một triệu.

def mark_sieve(sieve, x): 
    for i in range(x+x, len(sieve), x): 
     sieve[i] = False 

sieve = [True]*(10**7+1) 
for x in range(2, int(len(sieve)**0.5 + 1)): 
    if sieve[x]: mark_sieve(sieve, x) 

Ý tưởng là chúng tôi bước đầu tạo một danh sách gọi là sieve và gán tất cả các giá trị để True điều đó có nghĩa rằng chúng ta là cho bây giờ xem xét tất cả các số tới 1 triệu USD (bao gồm) như số nguyên tố. Chúng tôi sẽ lặp lại mỗi số lên một triệu và đánh dấu mọi số của nó là False trong danh sách sieve. Ngoài ra, để tối ưu hóa, chúng tôi chỉ lặp lại căn bậc hai là 1 triệu. Tại sao như vậy? Bởi vì một số không thể có hai yếu tố cả hai đều lớn hơn căn bậc hai của số. Vì vậy, nếu chúng ta chia một số bằng số nguyên cho đến khi trần căn bậc hai của nó và nó vẫn không phân chia được, điều đó có nghĩa là một nguyên tố của nó.

Vì vậy, nếu bạn muốn kiểm tra xem một số có phải là số nguyên tố hay không, bạn có thể sử dụng đơn giản sieve[some_number]. Nếu nó trả về False, nó không phải là số nguyên tố. Để có được một danh sách các số nguyên tố bạn có thể sử dụng [x for x in range(len(sieve)) if sieve[x]]

EDIT so sánh Speed ​​-

import timeit 
import math 

def isPrime(number): 
    if number<=1: 
     return False 
    if number==2: 
     return True 
    if number%2==0: 
     return False 
    for ind in range(3,int(math.sqrt(number))+1): 
     if number%ind==0: 
      return False 
    return True 

def mark_sieve(sieve, x): 
    for i in range(x+x, len(sieve), x): 
     sieve[i] = False 


# Other approaches 
time_0 = timeit.default_timer() 
primes = [] 
for i in range (1, 10**6+1): 
    if isPrime(i) == True: 
     primes.append(i) 
    else: 
     continue 

# Sieve Approach 
time_1 = timeit.default_timer() 
sieve = [True]*(10**6+1) 
sieve[0] = False #because we wont consider zero and one as primes 
sieve[1] = False 
for x in range(2, int(len(sieve)**0.5 + 1)): 
    if sieve[x]: mark_sieve(sieve, x) 

primes_2 = [x for x in range(len(sieve)) if sieve[x]] 

time_2 = timeit.default_timer() 
time_1-time_0 # 12.423080921173096 seconds 
time_2-time_1 # 0.9901950359344482 seconds 

Đối với một số 100.000, sử dụng sàng nhanh hơn 12 lần. Đối với một triệu tỷ lệ đó trở thành 90. Ngoài ra, khi sử dụng nhiều số lượng, tôi sẽ khuyên bạn nên chống lại các danh sách phụ thêm. Thay vào đó, hãy bắt đầu một danh sách và sau đó gán các giá trị.

Answer 5

Nếu bạn đang xây dựng danh sách số nguyên tố, bạn có thể sử dụng danh sách đó hiệu quả hơn như một phần của giải pháp.

Ví dụ, vòng lặp này:

for i in range(3, int(math.sqrt(number)) + 1): 

Đối thủ 1009 sẽ kiểm tra ~ 30 số nhưng chỉ có 10 nguyên tố ít hơn so với căn bậc hai của năm 1009 mà thực sự cần phải được kiểm tra. Và sự khác biệt này chỉ tiếp tục tăng lên.

Sử dụng danh sách thủ phát triển của chúng tôi như là một phần của giải pháp:

primes = [2] 

for number in range(3, 9999999 + 1, 2): # only test odd numbers 

    for prime in primes: 
     if prime * prime > number: # we're past sqrt, a prime! 
      primes.append(number) 
      break 

     if number % prime == 0: # a composite 
      break 

print(*primes[:10], '...', *primes[-10:]) 

Nowhere nhanh như rây @ ClockSlave, nhưng nhiều khả năng sẽ kết thúc trước khi rất nhiều các giải pháp khác.

Answer 6

Bây giờ nó hoạt động, tôi đã shortned các con số để 999

import math 

primes = [] 


def isPrime(number): 
    if number <= 1: 
     return False 
    for i in range(2, int(math.sqrt(number)) + 1): 
     if number % i == 0: 
      return False 
    return True 

for i in range(1, 999): 
    if isPrime(i): 
     primes.append(i) 

print(primes) 

[OUTPUT]:

[2, 3, 5, 7, 11, 13, 17 , 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 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, 307, 311, 313, 317, 331, 337, 34 7, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Answer 7

Thuật toán lấy tất cả các số nguyên tố trong [0,9999999] không hiệu quả lắm. Nó cần phải dành một thời gian dài để làm điều đó để bạn không thể nhìn thấy đầu ra khi bạn thực hiện nó. Chỉ vì nó chưa được thực hiện. Để có thuật toán nhanh hơn, bạn có thể kiểm tra this ra