Hướng dẫn check prime number in python without loop - kiểm tra số nguyên tố trong python mà không cần vòng lặp

Có cách nào khác để làm điều đó mà không cần sử dụng cho hoặc trong khi các vòng không?

Có, bạn có thể sử dụng chức năng đệ quy:recursive function:

def prime_number(n, d): if n//2 < d: return True if n%d == 0: return False return prime_number(n, d+1) def find_primes(n,i, result): if i == n + 1: return result if prime_number(i, 2): result.append(i) return find_primes(n, i+1, result) print(find_primes(100,2, []))

Đầu ra

[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]

Ngoài ra, bạn có thể đơn giản hóa [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] 4 bằng cách sử dụng [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] 5.

primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))]

Ví dụ để kiểm tra xem một số nguyên có phải là số nguyên tố hay không sử dụng cho vòng lặp và nếu ... câu lệnh khác. Nếu số không phải là nguyên tố, nó được giải thích trong đầu ra tại sao nó không phải là số nguyên tố.

Để hiểu ví dụ này, bạn nên có kiến ​​thức về các chủ đề lập trình Python sau:

• Python nếu ... tuyên bố khác
• Python cho vòng lặp
• Python nghỉ và tiếp tục

Một số nguyên dương lớn hơn 1 không có yếu tố nào khác ngoại trừ 1 và bản thân số được gọi là số nguyên tố. 2, 3, 5, 7, vv là số nguyên tố vì chúng không có bất kỳ yếu tố nào khác. Nhưng 6 không phải là nguyên tố (nó là tổng hợp) kể từ, [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] 6.

Ví dụ 1: Sử dụng biến cờ

# Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")

Trong chương trình này, chúng tôi đã kiểm tra xem Num có phải là nguyên tố hay không. Số ít hơn hoặc bằng 1 không phải là số nguyên tố. Do đó, chúng tôi chỉ tiến hành nếu num lớn hơn 1.

Chúng tôi kiểm tra xem Num có chính xác chia hết cho bất kỳ số nào từ [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] 7 đến [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] 8 không. Nếu chúng ta tìm thấy một yếu tố trong phạm vi đó, số không phải là số nguyên tố, vì vậy chúng ta đặt cờ thành [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] 9 và thoát ra khỏi vòng lặp.

Bên ngoài vòng lặp, chúng tôi kiểm tra xem primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 0 là [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] 9 hoặc primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 2.

• Nếu đó là [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] 9, primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 4 không phải là số nguyên tố.
• Nếu đó là primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 2, primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 4 là số nguyên tố.

Lưu ý: Chúng tôi có thể cải thiện chương trình của mình bằng cách giảm phạm vi số mà chúng tôi tìm kiếm các yếu tố.: We can improve our program by decreasing the range of numbers where we look for factors.

Trong chương trình trên, phạm vi tìm kiếm của chúng tôi là từ 2 đến [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] 8.

Chúng tôi có thể đã sử dụng phạm vi, primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 8 hoặc primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 9. Phạm vi thứ hai dựa trên thực tế là một số tổng hợp phải có hệ số nhỏ hơn hoặc bằng căn bậc hai của số đó. Nếu không, số là số nguyên tố.

Bạn có thể thay đổi giá trị của Biến số trong mã nguồn trên để kiểm tra xem một số là số nguyên tố hay không cho các số nguyên khác.

Trong Python, chúng ta cũng có thể sử dụng câu lệnh # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")0 để thực hiện nhiệm vụ này mà không cần sử dụng biến primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 0 bổ sung.

Ví dụ 2: Sử dụng một câu lệnh ...

# Program to check if a number is prime or not num = 407 # To take input from the user #num = int(input("Enter a number: ")) # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") # if input number is less than # or equal to 1, it is not prime else: print(num,"is not a prime number")

Đầu ra

407 is not a prime number 11 times 37 is 407

Ở đây, chúng tôi đã sử dụng một câu lệnh # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")2 để kiểm tra xem primes = [n for n in range(2, 50) if all(n % d for d in range(2, n))] 4 có phải là chính không.

Nó hoạt động theo logic rằng mệnh đề # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")4 của vòng lặp # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")5 chạy nếu và chỉ khi chúng ta không phá vỡ vòng lặp # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")5. Điều kiện đó chỉ được đáp ứng khi không tìm thấy yếu tố nào, điều đó có nghĩa là số đã cho là số nguyên tố.

Vì vậy, trong mệnh đề # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")4, chúng tôi in rằng số đó là số nguyên tố.

Hướng dẫn này sẽ dạy bạn cách viết chương trình Python để kiểm tra xem một số có chính hay không.number is prime or not.

Nếu bạn đã từng thực hiện các bài kiểm tra mã hóa, bạn sẽ bắt gặp câu hỏi toán học trong bài kiểm tra về tính nguyên thủy hoặc để kiểm tra xem một số là số nguyên tố. Và trong vài phút tiếp theo, bạn sẽ học cách đưa ra giải pháp tối ưu cho câu hỏi này.

Trong hướng dẫn này, bạn sẽ:

• Xem lại những điều cơ bản của các số nguyên tố,
• Viết mã python để kiểm tra xem một số là số nguyên tố và
• Tối ưu hóa nó thêm để có được thuật toán thời gian chạy O (√n).

Đối với tất cả điều này và hơn thế nữa, hãy để bắt đầu.

Một số nguyên tố là gì?

Hãy bắt đầu bằng cách xem xét những điều cơ bản của số nguyên tố.

Trong lý thuyết số, một số N tự nhiên được cho là chính nếu nó có chính xác hai yếu tố: 1 và chính số (n). Nhớ lại từ toán học của bạn: Một số tôi được cho là một yếu tố của số N, nếu tôi chia đều n. ✅n said to be prime if it has exactly two factors: 1 and the number itself (n). Recall from your school math: a number i is said to be a factor of the number n, if i divides n evenly. ✅

Bảng sau đây liệt kê một vài con số, tất cả các yếu tố của chúng và nếu chúng là nguyên tố.

N	Các nhân tố	Là Prime?
1	1	Không
2	1, 2	Đúng
3	1, 3	Đúng
4	1, 3	Không
7	1, 2	Đúng
15	1, 3	Không

1, 2

• Đúng
• 1, 3
• 1, 2, 4

1, 7

1, 3, 5, 15

Từ bảng trên, chúng ta có thể viết ra như sau:

2 là số nguyên tố nhỏ nhất.

1 là một yếu tố của mỗi số.

Mỗi số # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")8 là một yếu tố của chính nó.

Vì vậy, 1 và N là yếu tố tầm thường cho bất kỳ số n. Và một số nguyên tố không nên có bất kỳ yếu tố nào khác ngoài hai yếu tố này.

Điều này có nghĩa là khi bạn đi từ 2 đến N-1, bạn không thể tìm thấy một yếu tố không tầm thường phân chia N mà không có phần còn lại.

• Thuật toán O (N) để kiểm tra xem một số có chính trong Python khôngn evenly without a remainder, you can immediately conclude that the number is not prime.

• Trong phần này, chúng ta hãy chính thức hóa cách tiếp cận trên thành hàm Python.2 all the way up to n – 1 without finding a number that divides n evenly, then the number is prime.

Bạn có thể lặp qua tất cả các số từ 2 đến N - 1 bằng cách sử dụng đối tượng # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")9 trong Python.

Trong Python, # Program to check if a number is prime or not num = 407 # To take input from the user #num = int(input("Enter a number: ")) # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") # if input number is less than # or equal to 1, it is not prime else: print(num,"is not a prime number")0 trả về một đối tượng phạm vi. Sau đó, bạn có thể lặp lại đối tượng phạm vi để có được một chuỗi từ # Program to check if a number is prime or not num = 407 # To take input from the user #num = int(input("Enter a number: ")) # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") # if input number is less than # or equal to 1, it is not prime else: print(num,"is not a prime number")1 cho đến # Program to check if a number is prime or not num = 407 # To take input from the user #num = int(input("Enter a number: ")) # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") # if input number is less than # or equal to 1, it is not prime else: print(num,"is not a prime number")2 trong các bước của # Program to check if a number is prime or not num = 407 # To take input from the user #num = int(input("Enter a number: ")) # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") # if input number is less than # or equal to 1, it is not prime else: print(num,"is not a prime number")3.

def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return True

Vì chúng ta cần tập hợp các số nguyên từ 2 đến N-1, chúng ta có thể chỉ định # Program to check if a number is prime or not num = 407 # To take input from the user #num = int(input("Enter a number: ")) # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") # if input number is less than # or equal to 1, it is not prime else: print(num,"is not a prime number")4 và sử dụng nó kết hợp với vòng lặp # Program to check if a number is prime or not num = 29 # To take input from the user #num = int(input("Enter a number: ")) # define a flag variable flag = False # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2, num): if (num % i) == 0: # if factor is found, set flag to True flag = True # break out of loop break # check if flag is True if flag: print(num, "is not a prime number") else: print(num, "is a prime number")5.

• Ở đây, những gì chúng tôi muốn làm:n as the argument.
• Nếu bạn tìm thấy một số phân chia n đều mà không có phần còn lại, bạn có thể kết luận ngay rằng số không phải là số nguyên tố.
• Nếu bạn đã lặp qua toàn bộ phạm vi số từ 2 tất cả các cách lên đến N - 1 mà không tìm thấy một số chia đều n, thì số là số nguyên tố.

Chức năng Python để kiểm tra số nguyên tố

is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True

Sử dụng ở trên, chúng ta có thể tiếp tục và xác định hàm # Program to check if a number is prime or not num = 407 # To take input from the user #num = int(input("Enter a number: ")) # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") # if input number is less than # or equal to 1, it is not prime else: print(num,"is not a prime number")6 như sau.

Bây giờ, hãy để phân tích định nghĩa hàm trên.

Hàm trên # Program to check if a number is prime or not num = 407 # To take input from the user #num = int(input("Enter a number: ")) # prime numbers are greater than 1 if num > 1: # check for factors for i in range(2,num): if (num % i) == 0: print(num,"is not a prime number") print(i,"times",num//i,"is",num) break else: print(num,"is a prime number") # if input number is less than # or equal to 1, it is not prime else: print(num,"is not a prime number")6 có số nguyên dương N làm đối số.

Nếu bạn tìm thấy một yếu tố trong phạm vi được chỉ định là (2, N-1), hàm sẽ trả về ________ 22, vì số không phải là số nguyên tố.	Các nhân tố
6	Là Prime?3, 6
10	Không5, 10
18	1, 29, 18

Đúngn that is greater than n/2 is n itself.

1, 3

1, 2, 4

1, 7

1, 3, 5, 15

Từ bảng trên, chúng ta có thể viết ra như sau:

is_prime(9) # False is_prime(11) # True

Mặc dù có vẻ như chúng tôi đã tối ưu hóa, thuật toán này không hiệu quả hơn so với cái trước về độ phức tạp thời gian chạy. Trong thực tế, cả hai đều có độ phức tạp thời gian chạy O (N): tỷ lệ với giá trị của N hoặc tuyến tính trong n.O(n) runtime complexity: proportional to the value of n or linear in n.

Chúng ta có thể làm tốt hơn không? Vâng, chúng tôi có thể!

▶ Tiến hành phần tiếp theo để xác định cách cải thiện độ phức tạp về thời gian để kiểm tra số nguyên tố.

Thuật toán O (√n) để kiểm tra số nguyên tố trong Python

Nó xảy ra rằng các yếu tố của một số xảy ra theo cặp.

Nếu A là một yếu tố của số N, thì cũng tồn tại một yếu tố B sao cho a x b = n hoặc đơn giản, ab = n.a is a factor of the number n, then there also exists a factor b such that a x b = n, or simply, ab = n.

Hãy để xác minh điều này thông qua một ví dụ.

Bảng dưới đây cho thấy các yếu tố của số 18 xảy ra theo cặp. Bạn có thể xác minh tương tự cho một vài số nữa nếu bạn muốn.

Ngoài ra, lưu ý rằng √18 là khoảng 4.24.

Và trong các yếu tố xảy ra theo cặp (A, B), bạn có thể thấy rằng nếu A nhỏ hơn 4.24, thì B lớn hơn 4,24, trong ví dụ này, (2, 18) và (3, 6).(a, b), you can see that if a is less than 4.24, then b is greater than 4.24—in this example, (2, 18) and (3, 6).

một	b
1	18
2	9
3	6

Các yếu tố 18 theo cặp

Hình dưới đây cho thấy các yếu tố của 18 được vẽ trên dòng số.

Nếu số N xảy ra là một hình vuông hoàn hảo, bạn sẽ có a = b = √n là một trong những yếu tố.

Và trong các yếu tố xảy ra theo cặp (A, B), bạn có thể thấy rằng nếu A nhỏ hơn 4.24, thì B lớn hơn 4,24, trong ví dụ này, (2, 18) và (3, 6).

một	b
1	36
2	18
3	12
4	9
6	6

Các yếu tố 18 theo cặp

Hình dưới đây cho thấy các yếu tố của 18 được vẽ trên dòng số.

• Nếu số N xảy ra là một hình vuông hoàn hảo, bạn sẽ có a = b = √n là một trong những yếu tố.n can be written as n = a x b
• Và trong các yếu tố xảy ra theo cặp (A, B), bạn có thể thấy rằng nếu A nhỏ hơn 4.24, thì B lớn hơn 4,24, trong ví dụ này, (2, 18) và (3, 6).n is a perfect square, then a = b = √n.
• Các yếu tố của 36 theo cặpa < b, then, a < √n and b > √n.
• Tóm lại, chúng tôi có những điều sau đây:a > b, then a > √n and b < √n.

Mỗi số n có thể được viết là n = a x b

Nếu n là một hình vuông hoàn hảo, thì a = b = √n.

Nếu số N xảy ra là một hình vuông hoàn hảo, bạn sẽ có a = b = √n là một trong những yếu tố.

[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] 0

Khác, nếu a> b, thì a> √n và b