Kiểm tra xem có phải la số nguyên to không Python

Posted on by mtoplistChuyên mục:Top List

Kiểm tra xem có phải la số nguyên to không Python

Nội dung chính

Show

  • Số nguyên tố trong lập trình?
  • Bài toán số nguyên tố trong Python
  • Thuật toán
  • Hàm kiểm tra số nguyên tố
  • In ra số nguyên tố có trong danh sách
  • Lời kết
  • Giải trình
  • Phiên bản mở rộng
  • Video liên quan

Số nguyên tố trong ngôn ngữ Python là một dạng bài tập cơ bản nhất cho người mới học lập trình. Bài toán giúp bạn biết cách tạo một hàm, ứng dụng vòng for, câu điều kiện . . .

Số nguyên tố trong lập trình?

Trước tiên bạn cần phải hiểu số nguyên tố là gì?
Về mặt toán học, số nguyên tố là số chỉ có 2 ước là 1 và chính nó. Hay hiểu theo cách khác là nó chỉ chia hết cho 1 và chính nó.

Để viết được hàm kiểm tra số nguyên tố. Bạn cần phải áp dụng đúng tính chất toán học của nó, từ đó áp dụng vào thuật toán của mình. Sử dụng ngôn ngữ lập trình vận dụng linh hoạt các cấu trúc, cú pháp để hoàn thành được yêu cầu của bài toán.

Bài toán này dù dùng ngôn ngữ nào bạn cũng phải sử dụng đến cấu trúc vòng lặp, hoặc câu lệnh điều kiện. Cuối cùng là bạn phải kiểm tra xem số đó có chia hết cho số thứ 3 nào khác không.

Có một số tài liệu lập trình tiếng anh sẽ ghi số nguyên tố là: Prime number, bạn chú ý điều này nhé

Kiểm tra xem có phải la số nguyên to không Python

Bài toán số nguyên tố trong Python

Yêu cầu bài toán: Bạn hãy viết hàm kiểm tra một số nguyên có phải là số nguyên tố hay không bằng ngôn ngữ lập trình Python.
In ra danh sách các số nguyên tố có trong dãy (list ).

Thuật toán

Bạn cần phải viết một hàm kiểm tra trả về giá trị True hoặc False. Cách làm tương tự như lọc số nguyên tố trong C++. Tham số cần truyền vào là một số nguyên N.

  • Nếu tham số truyền vào nhỏ hơn 2 thì trả về giá trị False.
  • Sử dụng một vòng lặp chạy tử 2 đến nhỏ hơn hoặc bằng N/2 hoặc cũng có thể chạy tới sqrt(N). Nếu tìm thấy giá trị mà N chia hết thì trả về False.
  • Ngược lại trả về True.
    (Không tìm thấy giá trị nào mà N chia hết ngoài 1 và chính nó)

Ngoài ra còn có một cách thứ 2 tối ưu hơn là sử dụng sàng số nguyên tố. Nhưng cách này hơi khó hiểu hơn một chút. Bạn có thể tham khảo nó tại đây!

Với thuật toán mình đưa ra, khuyến khích bạn tự viết ra code trước khi tham khảo cách làm của mình nhé!

Hàm kiểm tra số nguyên tố

Đọc qua thuật toán thì thấy có vẻ khó nhưng khi ứng dụng thì cực kì đơn giản. Tham khảo mã code của mình dưới đây nhé! Mình viêt bằng Python 3. Nếu bạn viết Python 2 thì không cần sửa gì nhiều vì Python 3 chỉ thêm các dấu ngoặc . . .

# Ham kiem tra so nguyen to trong python
def Songuyento(n):
if(n<2): # neu n nho hon 2 thi tra ve False
return False
i=2;
while i <= n/2:
if(n%i == 0): # neu n chia het cho bat ki so nao thi tra ve Fasle
return False
i+=1
return True # nguoc lai tra ve True

In ra số nguyên tố có trong danh sách

Áp dụng hàm trên, mình viết thành một chương trình nhỏ hoàn chính bằng ngôn ngữ Python. Mình chỉ thêm một số câu lệnh in ra màn hình. Lời gọi đến hàm kiểm tra.

Code Python 3 hoàn chỉnh:

# Bai toan in ra cac so Nguyen to bang Python
def Songuyento(n): #Ham kiem tra so nt
if(n<2):
return False
i=2;
while i <= n/2:
if(n%i == 0):
return False
i+=1
return True
a=[1,4,6,7,8,11,13] # Khai bao mot list a
print(‘\n List A: ‘)
for i in a:
print (i, end=” “)
print(“\n”)
print(‘{:-^30}’.format(“KET QUA LOC SO NT”))
# Doan tren chi de in ra cho dep thoi ^^
for i in a:
if(Songuyento(i)): # Goi toi ham kiem tra
print(i, end= ” “)

Kết quả chạy chương trình bên trên:

Kiểm tra xem có phải la số nguyên to không Python

Lời kết

Mong rằng qua bài chia sẻ của mình, bạn có thể phần nào hiểu được về cách sử dụng, cấu trúc cú pháp của ngôn ngữ Python. Coi đây như là một bài toán luyện tập để cải thiện khả năng lập trình của mình.
Chúc các bạn thành công!

Nếu bạn nào chưa cài môi trường Python cho máy tính thì tải về ở đâynhé!

Đây là vấn đề của tôi:

from math import sqrt; from itertools import count, islice
def isPrime(n):
return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))

Đây là một thuật toán thực sự đơn giản và ngắn gọn, và do đó nó không có nghĩa là bất kỳ thứ gì gần với thuật toán kiểm tra tính nguyên thủy nhanh nhất hoặc tối ưu nhất. Nó có độ phức tạp về thời gian là O(sqrt(n)). Trụ sở tại đây để tìm hiểu thêm về các bài kiểm tra nguyên thủy được thực hiện đúng và lịch sử của chúng.

Giải trình

Tôi sẽ cung cấp cho bạn một số thông tin bên trong về dòng mã gần như bí truyền đó sẽ kiểm tra các số nguyên tố:

  • Trước hết, sử dụng range() thực sự là một ý tưởng tồi, bởi vì nó sẽ tạo ra một danh sách các số, sử dụng rất nhiều bộ nhớ. Sử dụng xrange() sẽ tốt hơn, bởi vì nó tạo ra trình tạo, chỉ cần ghi nhớ các đối số ban đầu bạn cung cấp và tạo mọi số khi đang di chuyển. Nếu bạn đang sử dụng Python 3 hoặc cao hơn range() đã được chuyển đổi thành trình tạo theo mặc định. Nhân tiện, đây hoàn toàn không phải là giải pháp tốt nhất: cố gắng gọi xrange(n) cho một số n sao cho n > 231-1 (là giá trị tối đa cho C long) tăng OverflowError. Do đó cách tốt nhất để tạo trình tạo phạm vi là sử dụng itertools:

    xrange(2147483647+1) # OverflowError
    from itertools import count, islice
    count(1) # Count from 1 to infinity with step=+1
    islice(count(1), 2147483648) # Count from 1 to 2^31 with step=+1
    islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3

  • Bạn thực sự không cần phải tìm đến n nếu bạn muốn kiểm tra xem n có phải là số nguyên tố hay không. Bạn có thể giảm đáng kể các bài kiểm tra và chỉ kiểm tra từ 2 xuống √(n) (căn bậc hai của n). Đây là một ví dụ:

    Hãy tìm tất cả các ước của n = 100 và liệt kê chúng trong một bảng:

    2 x 50 = 100
    4 x 25 = 100
    5 x 20 = 100
    10 x 10 = 100 <– sqrt(100)
    20 x 5 = 100
    25 x 4 = 100
    50 x 2 = 100

    Bạn sẽ dễ dàng nhận thấy rằng, sau căn bậc hai của n, tất cả các ước số mà chúng tôi tìm thấy đã thực sự được tìm thấy. Ví dụ: 20 đã được tìm thấy khi thực hiện 100/5. Căn bậc hai của một số là trung điểm chính xác nơi các ước số mà chúng ta tìm thấy bắt đầu được nhân đôi. Do đó, để kiểm tra xem một số có phải là số nguyên tố hay không, bạn sẽ chỉ cần kiểm tra từ 2 đến sqrt(n).

  • Tại sao lại là sqrt(n)-1, và không chỉ là sqrt(n)? Đó là bởi vì đối số thứ hai được cung cấp cho đối tượng itertools.islice là số lần lặp để thực hiện. islice(count(a), b) DỪNG SAU LẦN LẶP b. Đó là lý do tại sao:

    for number in islice(count(10), 2):
    print number,
    # Will print: 10 11
    for number in islice(count(1, 3), 10):
    print number,
    # Will print: 1 4 7 10 13 16 19 22 25 28

  • Hàm all(…) giống như sau:

    def all(iterable):
    for element in iterable:
    if not element:
    return False
    return True

    Nó có nghĩa đen kiểm tra tất cả các số trong iterable, trả về False khi một số ước tính thành False (có nghĩa là chỉ khi số đó bằng 0). Tại sao chúng ta sử dụng nó sau đó? Trước hết, chúng ta không cần sử dụng một biến chỉ mục bổ sung (giống như chúng ta sẽ sử dụng một vòng lặp), ngoài điều đó: chỉ để xử lý, không có nhu cầu thực sự của nó, nhưng có vẻ như nó chỉ cồng kềnh hơn một dòng mã thay vì một vài dòng lồng nhau.

Phiên bản mở rộng

Tôi đang bao gồm một phiên bản “giải nén” của hàm isPrime(), để dễ hiểu và đọc nó hơn:

from math import sqrt
from itertools import count, islice
def isPrime(n):
if n < 2:
return False
for number in islice(count(2), int(sqrt(n) – 1)):
if n % number == 0:
return False
return True

Đề bài: Viết chương trình sử dụng ngôn ngữ lập trình Python nhập vào một số nguyên bất kỳ. Kiểm tra số nguyên vừa nhập có phải là số nguyên tố hay không và hiển thị kết quả ra màn hình.

Yêu cầu kiến thức:

  • Nắm được cách tổ chức chương trình, phân chia thành các hàm
  • Nắm được cách phân tích và thiết kế chương trình, cách sử dụng vòng lặp trong Python
  • Hiểu và vận dụng được cách kiểm tra số nguyên tố

Code tham khảo dưới viết trên Python ver 3.8:

# Ho ten: Hoang Van Tuan
# Website: timoday.edu.vn
def KiemTra_NguyenTo(n):
“””
:param n: int
:return: True neu n la so nguyen to. False neu n khong la so nguyen to
“””
kt = True
if n < 2:
kt = False
elif n == 2:
kt = True
elif (n % 2) == 0:
kt = False
else:
for i in range(3, n, 2):
if (n % i) == 0:
kt = False
return kt
# Nhap du lieu
n = int(input(“Nhap vao so nguyen can kiem tra: “))
# Hien thi ket qua
if KiemTra_NguyenTo(n) is True:
print(n, “la so nguyen to!”)
else:
print(n, “khong la so nguyen to!”)

Kết luận:

  • Bạn có thể tham khảo thêm khóa học lập trình C từ cơ bản đến nâng cao. Xem tại đây
  • Bạn có thể tham khảo thêm khóa học Thành thạo lập trình C#. Xem tại đây

mtoplist