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) vì, # 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.
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ừ # 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 đế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")5 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 # 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 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 # 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")7 là # 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 hoặc # 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")9.
- Nếu đó là # 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, 407 is not a prime number 11 times 37 is 4071 không phải là số nguyên tố.
- Nếu đó là # 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")9, 407 is not a prime number 11 times 37 is 4071 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 # 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")5.
Chúng tôi có thể đã sử dụng phạm vi, 407 is not a prime number 11 times 37 is 4075 hoặc 407 is not a prime number 11 times 37 is 4076. 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 407 is not a prime number 11 times 37 is 4077 để thực hiện nhiệm vụ này mà không cần sử dụng biế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")7 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 407 is not a prime number 11 times 37 is 4079 để kiểm tra xem 407 is not a prime number 11 times 37 is 4071 có phải là chính không.
Nó hoạt động theo logic rằng mệnh đề # Python program to display all the prime numbers within an interval lower = 900 upper = 1000 print("Prime numbers between", lower, "and", upper, "are:") for num in range(lower, upper + 1): # all prime numbers are greater than 1 if num > 1: for i in range(2, num): if (num % i) == 0: break else: print(num)1 của vòng lặp # Python program to display all the prime numbers within an interval lower = 900 upper = 1000 print("Prime numbers between", lower, "and", upper, "are:") for num in range(lower, upper + 1): # all prime numbers are greater than 1 if num > 1: for i in range(2, num): if (num % i) == 0: break else: print(num)2 chạy nếu và chỉ khi chúng ta không phá vỡ vòng lặp # Python program to display all the prime numbers within an interval lower = 900 upper = 1000 print("Prime numbers between", lower, "and", upper, "are:") for num in range(lower, upper + 1): # all prime numbers are greater than 1 if num > 1: for i in range(2, num): if (num % i) == 0: break else: print(num)2. Đ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 điều khoản # Python program to display all the prime numbers within an interval lower = 900 upper = 1000 print("Prime numbers between", lower, "and", upper, "are:") for num in range(lower, upper + 1): # all prime numbers are greater than 1 if num > 1: for i in range(2, num): if (num % i) == 0: break else: print(num)1, chúng tôi in rằng số đó là số nguyên tố.
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) vì, # 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.
Mã nguồn
# Python program to display all the prime numbers within an interval lower = 900 upper = 1000 print("Prime numbers between", lower, "and", upper, "are:") for num in range(lower, upper + 1): # all prime numbers are greater than 1 if num > 1: for i in range(2, num): if (num % i) == 0: break else: print(num)Đầu ra
Prime numbers between 900 and 1000 are: 907 911 919 929 937 941 947 953 967 971 977 983 991 997Ở đây, chúng tôi lưu trữ khoảng thời gian dưới mức thấp hơn cho khoảng dưới và trên cho khoảng trên và tìm số nguyên tố trong phạm vi đó. Truy cập trang này để tìm hiểu làm thế nào để kiểm tra xem một số có chính hay không.
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ố # Python program to display all the prime numbers within an interval lower = 900 upper = 1000 print("Prime numbers between", lower, "and", upper, "are:") for num in range(lower, upper + 1): # all prime numbers are greater than 1 if num > 1: for i in range(2, num): if (num % i) == 0: break else: print(num)6 là một yếu tố của chính nó.
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 Prime numbers between 900 and 1000 are: 907 911 919 929 937 941 947 953 967 971 977 983 991 997 2 và sử dụng nó kết hợp với vòng lặp # Python program to display all the prime numbers within an interval lower = 900 upper = 1000 print("Prime numbers between", lower, "and", upper, "are:") for num in range(lower, upper + 1): # all prime numbers are greater than 1 if num > 1: for i in range(2, num): if (num % i) == 0: break else: print(num)2.
Ở đây, những gì chúng tôi muốn làm:
- 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 evenly without a remainder, you can immediately conclude that the number is not prime.
- 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ố.2 all the way up to n – 1 without finding a number that divides n evenly, then the number is prime.
Chức năng Python để kiểm tra số nguyên tố
Sử dụng ở trên, chúng ta có thể tiếp tục và xác định hàm Prime numbers between 900 and 1000 are: 907 911 919 929 937 941 947 953 967 971 977 983 991 997 4 như sau.
def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return TrueBây giờ, hãy để phân tích định nghĩa hàm trên.
- Hàm trên Prime numbers between 900 and 1000 are: 907 911 919 929 937 941 947 953 967 971 977 983 991 997 4 có số nguyên dương N làm đối số.n as the argument.
- 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ề ________ 19, vì số không phải là số nguyên tố.
- Và nó trả về # 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 nếu bạn đi qua toàn bộ vòng lặp mà không tìm thấy một yếu tố.
Tiếp theo, hãy để gọi cho chức năng với các đối số và xác minh xem đầu ra có chính xác không.
is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # TrueTrong đầu ra ở trên, bạn thấy rằng 2 và 11 là số nguyên tố (hàm trả về # 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). Và 8 và 9 không phải là số nguyên tố (hàm trả về # 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")9).
Cách tối ưu hóa hàm Python is_prime ()
Chúng ta có thể làm một tối ưu hóa nhỏ ở đây. Quan sát danh sách các yếu tố trong bảng dưới đây.
| Con số | Các nhân tố |
| 6 | 1, 2, 3, 63, 6 |
| 10 | 1, 2, 5, 105, 10 |
| 18 | 1, 2, 3, 6, 9, 189, 18 |
Chà, chúng ta có thể thấy rằng yếu tố duy nhất của n lớn hơn n/2 là chính n.n that is greater than n/2 is n itself.
Vì vậy, điều này có nghĩa là bạn không phải lặp lại tất cả các cách lên đến N - 1. Thay vào đó, bạn chỉ có thể chạy vòng lặp lên đến n/2.
Nếu bạn không tìm thấy một yếu tố không tầm thường cho đến N/2, bạn cũng có thể tìm thấy một yếu tố ngoài N/2.
Bây giờ, hãy để sửa đổi chức năng Prime numbers between 900 and 1000 are: 907 911 919 929 937 941 947 953 967 971 977 983 991 997 4 để kiểm tra các yếu tố trong phạm vi (2, n/2)
def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return TrueHãy để Lừa đi trước và xác minh đầu ra thông qua một vài cuộc gọi chức năng.
is_prime(9) # False is_prime(11) # TrueMặ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 |
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ố.
▶️ Look at the factors of 36 in the table below. As 36 is a perfect square, a = b = 6 is one of the factors. For all other factor pairs (a, b), a < 6 and b > 6 holds.
| một | b |
| 1 | 36 |
| 2 | 18 |
| 3 | 12 |
| 4 | 9 |
| 6 | 6 |
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
- If 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.
Let’s proceed to optimize the function to check for prime numbers in Python.
import math def is_prime(n): for i in range(2,int(math.sqrt(n))+1): if (n%i) == 0: return False return TrueKhác, nếu a> b, thì a> √n và b