Số nguyên tố trong python

Số nguyên tố là số tự nhiên lớn hơn 1 và không có ước nào ngoài 1 và chính nó. Bạn có thể viết một mã bằng Python sẽ giúp bạn tìm tất cả các số nguyên tố. Trong bài viết này, chúng ta sẽ xem cách viết chương trình số nguyên tố bằng Python theo trình tự sau

Bắt đầu nào

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

Số nguyên dương lớn hơn 1 không có ước nào khác ngoài 1 và chính nó được gọi là số nguyên tố. Các số 2, 3, 5, 7, v.v. là các số nguyên tố vì chúng không có thừa số nào khác. Để tìm một số nguyên tố trong Python, bạn phải lặp lại giá trị từ đầu đến cuối bằng vòng lặp for và với mỗi số, nếu nó lớn hơn 1, hãy kiểm tra xem nó có chia hết cho n không. Nếu chúng tôi tìm thấy bất kỳ số nào khác chia, hãy in giá trị đó

Tìm hiểu khóa đào tạo Python của chúng tôi tại các thành phố/quốc gia hàng đầu

Chương trình Python để kiểm tra số nguyên tố

Số nguyên tố luôn dương và nó sẽ được kiểm tra ngay từ đầu chương trình. Tại đây, bạn sẽ chia số vừa nhập cho tất cả các số để xem có ước dương nào khác ngoài 1 và chính số đó không. Nếu tìm thấy bất kỳ ước số nào thì chúng tôi hiển thị rằng "số không phải là số nguyên tố" ngược lại chúng tôi hiển thị rằng "số là số nguyên tố"

chương trình Python

num = 13
if num > 1:
for i in range(2, num//2):
if (num % i) == 0:
print(num, "is not a prime number")
break
else:
print(num, "is a prime number")
else:
print(num, "is not a prime number")

đầu ra. 13 là một số nguyên tố

Phương pháp tối ưu hóa

Có nhiều cách khác nhau để tối ưu hóa chương trình số nguyên tố trong Python

• Thay vì kiểm tra đến n, chúng ta có thể kiểm tra đến √n vì thừa số lớn hơn của n phải là bội số của thừa số nhỏ hơn đã được kiểm tra
• Thuật toán có thể được cải thiện hơn nữa bằng cách quan sát rằng tất cả các số nguyên tố đều có dạng 6k ± 1, ngoại trừ 2 và 3. Điều này là do tất cả các số nguyên có thể được biểu diễn dưới dạng (6k + i) đối với một số nguyên k và với i = ?1, 0, 1, 2, 3 hoặc 4; . Vì vậy, một phương pháp hiệu quả hơn là kiểm tra xem n có chia hết cho 2 hay 3 hay không, sau đó kiểm tra tất cả các số có dạng 6k ± 1

Ví dụ

def isPrime(n) :
if (n <= 1) :
return False
if (n <= 3) :
return True
if (n % 2 == 0 or n % 3 == 0) :
return False
i = 5
while(i * i <= n) :
if (n % i == 0 or n % (i + 2) == 0) :
return False
i = i + 6
return True
if (isPrime(11)) :
print(" true")
else :
print(" false")
if(isPrime(15)) :
print(" true")
else :
print(" false")

Với điều này, chúng tôi đã đi đến cuối bài viết của chúng tôi. Tôi hy vọng bạn đã hiểu cách viết chương trình số nguyên tố trong Lập trình Python

Để có kiến ​​thức chuyên sâu về Python cùng với các ứng dụng khác nhau của nó, bạn có thể đăng ký Khóa đào tạo cấp chứng chỉ Python trực tiếp với sự hỗ trợ 24/7 và quyền truy cập trọn đời.  

Có một câu hỏi cho chúng tôi?

Đi đầu trong lĩnh vực công nghệ với Chương trình Sau đại học về AI và Học máy này với sự hợp tác của Học viện E&ICT, Viện Công nghệ Quốc gia, Warangal. Khóa học Trí tuệ nhân tạo này được tuyển chọn để mang lại kết quả tốt nhất

Số nguyên tố là tập hợp con của các số tự nhiên mà ước của nó chỉ bằng 1 và chính nó. Tại sao chúng ta lo lắng về số nguyên tố và thu được số nguyên tố? . Bắt đầu nào.  

Thừa số của một số đã cho là những số mà phép chia cho kết quả là số dư bằng 0. Đây là những điều quan trọng hàng đầu trong lĩnh vực mật mã để kích hoạt khóa công khai và khóa riêng. Về cơ bản, ngày nay internet ổn định nhờ mật mã và nhánh này chủ yếu dựa vào các số nguyên tố.  

1 có phải là số nguyên tố không?

Chúng ta hãy lùi lại một bước và chú ý đến định nghĩa của các số nguyên tố. Chúng được định nghĩa là 'các số tự nhiên lớn hơn 1 không thể được thành lập bằng cách nhân hai số tự nhiên nhỏ hơn'. Số tự nhiên lớn hơn 1 nhưng không phải là số nguyên tố gọi là hợp số.  

Do đó, chúng ta không thể đưa 1 vào danh sách các số nguyên tố. Tất cả các danh sách các số nguyên tố bắt đầu bằng 2. Vậy số nguyên tố nhỏ nhất là 2 chứ không phải 1

số nguyên tố cùng nhau

Hãy để chúng tôi tìm hiểu thêm. Nếu chúng ta có hai số nguyên tố thì sao? . Do đó, mọi cặp số nguyên tố đều dẫn đến các số nguyên tố cùng nhau. Các số nguyên tố cùng nhau là cặp số có ước chung lớn nhất bằng 1. Chúng ta cũng có thể có các cặp số không nguyên tố và các cặp số nguyên tố và không nguyên tố. Ví dụ, xem xét số cặp

1. (25, 36)
2. (48, 65)
3. (6,25)
4. (3,2)

Kiểm tra xem Chuỗi đã cho có phải là Palindrome trong Python không

Số nguyên tố nhỏ nhất và lớn nhất

Bây giờ chúng ta đã xem xét các số nguyên tố, phạm vi của các số nguyên tố là gì?

Số nguyên tố lớn nhất có thể là gì?

Vâng, điều này có một số câu đố thú vị liên quan đến nó. Vào năm 2018, Patrick Laroche của Great Internet Mersenne Prime Search đã tìm thấy số nguyên tố lớn nhất, 282.589.933 − 1, một số có 24.862.048 chữ số khi viết ở cơ số 10. Đó là một con số khổng lồ.  

Bây giờ chúng ta hãy tập trung vào giải các bài toán liên quan đến số nguyên tố. Những báo cáo vấn đề như sau

1. Nhận biết chúng có phải là số nguyên tố hay không
2. Lấy tập hợp các số nguyên tố giữa một dãy số
3. Nhận biết chúng có phải là số nguyên tố hay không

Điều này có thể được thực hiện theo hai cách. Chúng ta hãy xem xét phương pháp đầu tiên. Kiểm tra tất cả các số giữa 2 và chính số đó để tìm thừa số. Hãy để chúng tôi thực hiện tương tự. Luôn bắt đầu với thuật toán sau-

thuật toán

1. Khởi tạo vòng lặp for bắt đầu từ số 2 và kết thúc ở số
2. Kiểm tra xem số đó có chia hết cho 2 không
3. Lặp lại cho đến khi số -1 được kiểm tra
4. Trong trường hợp, số đó chia hết cho bất kỳ số nào thì số đó không phải là số nguyên tố
5. Khác, nó là một số nguyên tố

num = int(input("Enter the number: "))

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")

Hãy để chúng tôi xem xét giải pháp hiệu quả, trong đó chúng tôi có thể giảm tính toán xuống một nửa. Chúng tôi chỉ kiểm tra các thừa số cho đến căn bậc hai của số. Xem xét 36. thừa số của nó là 1,2,3,4,6,9,12,18 và 36

Căn bậc hai của 36 là 6. Cho đến 6, có 4 yếu tố ngoài 1. Do đó, nó không phải là số nguyên tố

Xem xét 73. Căn bậc hai của nó là 8. 5. Chúng tôi làm tròn nó đến 9. Không có thừa số nào ngoài 1 cho 73 đến 9. Do đó nó là số nguyên tố

Bây giờ trước khi chúng ta tìm hiểu chi tiết về Chương trình Python cho số nguyên tố, có thể tham gia một khóa bồi dưỡng miễn phí về Nguyên tắc cơ bản của Python. Khóa học này bao gồm tất cả các khái niệm cơ bản và nâng cao về lập trình Python như Cấu trúc dữ liệu Python, Biến, Toán tử, Câu lệnh điều khiển luồng và OOP. Nó thậm chí còn cung cấp chứng chỉ khi hoàn thành, điều này chắc chắn có thể thúc đẩy sơ yếu lý lịch của bạn

Chương trình Python cho số nguyên tố

Hãy để chúng tôi triển khai logic trong python–

thuật toán

1. Khởi tạo vòng lặp for bắt đầu từ 2 kết thúc ở giá trị nguyên sàn của căn bậc hai của số
2. Kiểm tra xem số đó có chia hết cho 2 không
3. Lặp lại cho đến khi căn bậc hai của số được kiểm tra
4. Trong trường hợp, số đó chia hết cho bất kỳ số nào thì số đó không phải là số nguyên tố
5. Khác, nó là một số nguyên tố

import math

def primeCheck(x):
sta = 1
for i in range(2,int(math.sqrt(x))+1): # range[2,sqrt(num)]
if(x%i==0):
sta=0
print("Not Prime")
break
else:
continue
if(sta==1):
print("Prime")
return sta

num = int(input("Enter the number: "))
ret = primeCheck(num)

Chúng tôi xác định một hàm primeCheck nhận đầu vào là số cần kiểm tra và trả về trạng thái. Một biến là một biến nhận 0 hoặc 1

Ta xét bài toán nhận biết số nguyên tố trong dãy cho trước

thuật toán

1. Khởi tạo vòng lặp for giữa phạm vi dưới và trên
2. Sử dụng hàm primeCheck để kiểm tra một số có phải là số nguyên tố hay không
3. Nếu không phải là số nguyên tố, hãy ngắt vòng lặp thành vòng lặp bên ngoài tiếp theo
4. Nếu đầu tiên, in nó
5. Chạy vòng lặp for cho đến khi đạt đến upperRange

l_range = int(input("Enter Lower Range: "))
u_range = int(input("Enter Upper Range: "))
print("Prime numbers between", l_range, "and", u_range, "are:")
for num in range(l_range, u_range + 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)

Trong hướng dẫn này, chúng tôi đã đề cập đến mọi chủ đề liên quan đến số nguyên tố. Chúng tôi hy vọng bạn thích đọc bài viết. Để biết thêm các bài viết về học máy và python, hãy theo dõi

Công thức tìm số nguyên tố trong Python là gì?

Số nguyên tố trong Python w3schools là gì?

Thừa số nguyên tố trong Python là gì?

Có thư viện số nguyên tố trong Python không?