O₂ Education

Tag: số nguyên tố

  • 100+ Bài tập Python cơ bản có lời giải

    100+ Bài tập Python cơ bản có lời giải

    Mời bạn xem phiên bản đầy đủ tại đây https://divin.dev/python/2022/03/14/20-bai-tap-python.html

    Mời bạn xem thêm Bài tập Python cơ bản lớp 10 được chia theo từng chủ đề.

    Bài tập Python cơ bản

    Bài 1. In toàn bộ các số chẵn từ 1000 đến 2000.

    even_numbers=[]

for i in range(1000, 2001):
    if (i%2=0):
        even_numbers.append(str(i))
print (','.join(even_numbers))

    Bài 2. Viết chương trình tìm tất cả các số chia hết cho 7 nhưng không phải bội số của 5, nằm trong đoạn 2000 và 3200 (tính cả 2000 và 3200). Các số thu được sẽ được in thành chuỗi trên một dòng, cách nhau bằng dấu phẩy.

    j=[] for i in range(2000, 3201):
  if (i%7==0) and (i%5!=0):
    j.append(str(i))
print (','.join(j))

    Nếu chỉ cần in ra màn hình kết quả, chúng ta có thể không cần sử dụng List.

    for i in range(2000, 3201):
    if (i % 7 == 0) and (i % 5 != 0):
        print(i, end=' ')

    Bài 3. Viết một chương trình có thể tính giai thừa của một số cho trước. Kết quả được in thành chuỗi trên một dòng, phân tách bởi dấu phẩy. Ví dụ, số cho trước là 8 thì kết quả đầu ra phải là 40320.

    n = int(input("Nhập số cần tính giai thừa:")) 
def fact(n):
    if n==0:
        return 1
    else:
        return n*fact(n-1)
print(fact(n))

    Nếu chỉ sử dụng vòng lặp, không sử dụng hàm và lời gọi đệ quy, ta có thể làm như sau:

    n = int(input('Enter a number '))
factorial = 1
for i in range(1,n+1):
    factorial *= i
print(factorial)

    Bài 4. Với số nguyên n nhất định, hãy viết chương trình để tạo ra một dictionary chứa (i, i*i) như là số nguyên từ 1 đến n (bao gồm cả 1 và n) sau đó in ra dictionary này. Ví dụ: Giả sử số n là 8 thì đầu ra sẽ là: {1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64}.

    n = int(input('Enter a number '))
d = dict()
for i in range(1, n+1):
    d[i] = i*i
print(d)

    Bài 5. Viết chương trình chấp nhận một chuỗi số, phân tách bằng dấu phẩy từ giao diện điều khiển, tạo ra một List  và một tuple chứa mọi số.

    Ví dụ: Đầu vào được cung cấp là 34,67,55,33,12,98 thì đầu ra là:

    ['34', '67', '55', '33', '12', '98']
    ('34', '67', '55', '33', '12', '98')

    Chương trình này chỉ đơn giản là sử dụng hàm split() và chuyển một List sang một tuple.

    values=input("Nhập vào các giá trị:") 
l=values.split(",") 
t=tuple(l) 
print (l) 
print (t)

    Bài 6. Viết một hàm tính giá trị bình phương của một số.

    # square of a number
x = int(input("Enter a number: "))
def square(x):
    return x * x

    Bài 7. Viết chương trình tính số Fibonacci thứ n, với n nhập vào từ bàn phím.

    # find fibonacci number
n = int(input("Enter a number: "))
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

    Bài 8. Viết một chương trình nhập vào một danh sách các số và tạo một danh sách mới chỉ gồm phần tử đầu tiên và cuối cùng của danh sách đó. Viết chương trình sử dụng hàm.

    Ví dụ, nhập vào danh sách [5, 10, 15, 20, 25] thì kết quả trả về là danh sách [5, 25]

    def list_ends(a_list):
    return [a_list[0], a_list[len(a_list)-1]]

    Bài 9. Viết một hàm nhận vào ba số thực và trả về số lớn nhất trong ba số. Lưu ý, không sử dụng hàm max() của Python.

    # max of three numbers
def max_of_three(a, b, c):
    if a > b:
        if a > c:
            return a
        else:
            return c
    else:
        if b > c:
            return b
        else:
            return c

    Bài 10. Viết chương trình yêu cầu người dùng nhập vào một chuỗi và in ra màn hình thông báo chuỗi đó có phải là chuỗi palindrome hay không. (Chuỗi Palindrome là một chuỗi mà đọc xuôi và ngược đều như nhau, ví dụ ABCDCBA.)

    Cách giải thứ nhất, sử dụng cách đảo ngược xâu:

    wrd=input("Please enter a word")
wrd=str(wrd)
rvs=wrd[::-1]
print(rvs)
if wrd == rvs:
    print("This word is a palindrome")
else:
    print("This word is not a palindrome")

    Cách thứ hai, sử dụng vòng lặp for

    def reverse(word):
   x = ''
   for i in range(len(word)):
      x += word[len(word)-1-i]
   return x

word = input('give me a word:\n')
x = reverse(word)
if x == word:
   print('This is a Palindrome')
else:
   print('This is NOT a Palindrome')

    Bài 11. Viết chương trình hỏi người dùng một số tự nhiên n và in ra tất cả ước số của con số đó.

    n = int(input("Enter a number: "))
for i in range(1, n + 1):
    if n % i == 0:
        print(i)

    Bài 12. Viết một chương trình (sử dụng các hàm) yêu cầu người dùng nhập một chuỗi dài gồm nhiều từ. In lại cho người dùng một chuỗi mới với thứ tự từ ngữ được đảo ngược lại với thứ tự ban đầu. Ví dụ, khi người dùng nhập chuỗi: Toi la Phuong thì in ra màn hình Phuong la Toi

    sentense = input("Enter a sentence: ")
words = sentence.split()
words.reverse()
sentence = " ".join(words)
print(sentence)

    Bài 13. Viết chương trình kiểm tra xem số n có là số nguyên tố hay không.

    # check prime number
n = int(input("Enter a number: "))
for i in range(2, n):
    if n % i == 0:
        print("Not a prime number")
        break
else:
    print("Prime number")

    Bài 14. Viết một chương trình nhập vào hai số tự nhiên m, n. In ra màn hình mảng hai chiều mà phần tử trong hàng thứ i và cột thứ j của mảng là i*j.

    Ví dụ: Giá trị m, n nhập vào là 3 và 5 thì đầu ra là: [[0, 0, 0, 0, 0], [0, 1, 2, 3, 4], [0, 2, 4, 6, 8]]

    m, n = map(int, input('Enter two numbers: ').split())
array2 = [[0 for i in range(n)] for j in range(m)]
for row in range(m):
    for col in range(n):
        array2[row][col] = row * col
print(array2)

    Bài 15. Viết một chương trình nhận chuỗi từ do người dùng nhập vào, phân tách nhau bởi dấu phẩy và in những từ đó thành chuỗi theo thứ tự bảng chữ cái, phân tách nhau bằng dấu phẩy.

    Giả sử đầu vào được nhập là: without,hello,bag,world thì đầu ra sẽ là bag,hello,without,world.

    items=[x for x in input("Nhập một chuỗi: ").split(',')]
items.sort()
print (','.join(items))

    Bài 16. Viết chương trình giải phương trình bậc hai $ax^2+bx+c=0$ với a, b, c là số nguyên và được nhập vào từ bàn phím.

    a, b, c = map(int, input('Nhập a, b, c cách nhau bằng dấu cách: ').split())
if a == 0:
    if b == 0:
        if c == 0:
            print("Phương trình có vô số nghiệm")
        else:
            print("Phương trình vô nghiệm")
    else:
        print("Phương trình có một nghiệm x =", -c/b)
else:
    delta = b**2 - 4*a*c
    if delta < 0:
        print("Phương trình vô nghiệm")
    elif delta == 0:
        print("Phương trình có nghiệm kép x1 = x2 =", -b/(2*a))
    else:
        print("Phương trình có 2 nghiệm phân biệt x1 =", (-b + delta**0.5)/(2*a), "và x2 =", (-b - delta**0.5)/(2*a))

    Bài 17. Viết chương trình tính tổng của các chữ số của môt số nguyên dương n trong Python. Số nguyên dương n được nhập từ bàn phím.

    def totalDigitsOfNumber(n):
    total = 0;
    while (n > 0):
        total = total + n % 10;
        n = int(n / 10);
    return total;
 
n = int(input("Nhập số nguyên dương n = "));
print("Tổng các chữ số của", n , "là", totalDigitsOfNumber(n));

    Bài 18. Viết chương trình sinh các xâu nhị phân có độ dài n.

    Xem lời giải tại đây Thuật toán sinh các dãy nhị phân có độ dài n

    Bài 19. Viết chương trình giải bài toán Bài toán Tháp Hà Nội (Tower of Hanoi)

    Bài 20. Viết chương trình phân tích số nguyên dương n thành thừa số nguyên tố.

    def phanTichSoNguyen(n):
    i = 2;
    listNumbers = [];
    # phân tích
    while (n > 1):
        if (n % i == 0):
            n = int(n / i);
            listNumbers.append(i);
        else:
            i = i + 1;
    # nếu listNumbers trống thì add n vào listNumbers
    if (len(listNumbers) == 0):
        listNumbers.append(n);
    return listNumbers;
 
n = int(input("Nhập số nguyên dương n = "));

listNumbers = phanTichSoNguyen(n);
size = len(listNumbers);
sb = "";
for i in range(0, size - 1):
    sb = sb + str(listNumbers[i]) + " x ";
sb = sb + str(listNumbers[size-1]);
# in kết quả ra màn hình
print("Kết quả:", n, "=", sb);

    Bài 21. Định nghĩa một class có ít nhất 2 method:

    • getString: để nhận một chuỗi do người dùng nhập vào từ giao diện điều khiển.
    • printString: in chuỗi vừa nhập sang chữ hoa.

    Thêm vào các hàm hiểm tra đơn giản để kiểm tra method của class.

    Ví dụ: Chuỗi nhập vào là o2.edu.vn thì đầu ra phải là O2.EDU.VN

    class InputOutString(object):
   def __init__(self):
       self.s = ""

   def getString(self):
       self.s = input("Nhập chuỗi:")
   def printString(self):
       print (self.s.upper())

strObj = InputOutString()
strObj.getString()
strObj.printString()

    Bài 22. Viết chương trình Python tính tổng các phần tử của một danh sách.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]
for i in range(0,n): print(a[i],' ',end='')
print()

tong=0
for i in range(0,n):
    tong+=a[i]
print('Tổng =',tong)

    Bài 23. Viết chương trình Python đếm số lượng các số hạng dương và tổng của các số hạng dương.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

dem=0
tongd=0
for i in range(0,n):
    if a[i]>0:
       dem+=1
       tongd+=a[i]
print('Số hạng dương:',dem)
print('Tổng số dương:',tongd)

    Hoặc có thể sử dụng hàm:

    def count_positive_numbers_and_sum(numbers):
    count = 0
    sum = 0
    for number in numbers:
        if number > 0:
            count += 1
            sum += number
    return count, sum

# Sử dụng hàm trên với một danh sách các số nguyên bất kỳ
numbers = [1, 2, 3, -4, -5, 6, 7, -8, 9]
count, sum = count_positive_numbers_and_sum(numbers)

print("Số lượng các số hạng dương là:", count)
print("Tổng các số hạng dương là:", sum)

    Bài 24. Viết chương trình Python tính trung bình cộng của cả danh sách, trung bình cộng các phần tử dương trong danh sách.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

for i in range(0,n):tong+=a[i]
print('Trung bình cộng của danh sách:',tong)
dem=0
tongd=0
for i in range(0,n):
    if a[i]>0:
       dem+=1
       tongd+=a[i]
print('Trung bình cộng các số dương:',tongd/dem)

    Bài 25. Viết chương trình Python tìm vị trí của phần tử âm đầu tiên trong danh sách.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

i=0
while a[i]>=0:
    i+=1
    if i==n:
       break
if i==n:
    print('Không có phần tử âm')
else:
    print('Vị trí phần tử âm đầu tiên:',i+1)

    Bài 26. Viết chương trình Python tìm vị trí của phần tử dương cuối cùng trong danh sách.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]
i=n-1
while a[i]<=0:
   i-=1
   if i==-1:
      break
if i==-1:
    print('Không có phần tử dương')
else:
    print('Vị trí phần tử dương cuối cùng:',i+1)

    Bài 27. Viết chương trình Python tìm phần tử lớn nhất của danh sách và vị trí phần tử lớn nhất cuối cùng.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

max=a[0]
vt=0
for i in range(1,n-1):
    if a[i]>max:
        max=a[i]
        vt=i
print('Số lớn nhất là',max,'tại vị trí',vt+1)

    Bài 28. Viết chương trình Python tìm phần tử lớn thứ nhì của danh sách và các vị trí của các phần tử đạt giá trị lớn nhì.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

B=a.copy()
m=max(B)
i=0
while i<len(B):
    if B[i]==m:
        B.remove(B[i])
        i-=1
    i+=1
if len(B)==0:
    print("Khong co so lon nhi")
else:
    m=max(B)
    print("So lon nhi la",m,"tai vi tri",end=" ")
    for i in range(len(a)):
        if a[i]==m:
            print(i+1,end=", ")

    Bài 29. Viết chương trình Python tính số lượng các số dương liên tiếp nhiều nhất.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

d=len(a)
i=0
maxd=0
while i<d:
    while a[i]<=0:
        i+=1
        if i==d:break
    if i<d:
        max1=0
        j=i
        while a[j]>0:
            max1+=1
            j+=1
            if j==d: break
        if max1>maxd: 
            maxd=max1
        i=j
    i+=1
print('So duong lien tiep dai nhat =',maxd)

    Bài 30. Viết chương trình Python tính số lượng các số dương liên tiếp có tổng lớn nhất.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

d=len(a)
i=0
sumd=0
while i<d:
    while a[i]<=0:
        i+=1
        if i==d:break
    if i<d:
        sum1=0
        j=i
        while a[j]>0:
            sum1+=a[j]
            j+=1
            if j==d: break
        if sum1>sumd: 
            sumd=sum1
        i=j
    i+=1
print('Tong so duong lien tiep dai nhat =',sumd)

    Bài 31. Viết chương trình Python tính số lượng các phần tử liên tiếp đan dấu nhiều nhất (dãy phần tử liên tiếp được gọi là đan dấu nếu tích hai phần tử liên tiếp âm).

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

d=len(a)
i=0
maxdd=0
for i in range(d-1):
    max1=0
    while a[i]*a[i+1]<0:
        max1+=1
        i+=1
        if i==d-1:break
    if max1>maxdd: maxdd=max1
if maxdd>0: maxdd+=1
print('Day so dan dau dai nhat =',maxdd)

    Bài 32. Viết chương trình Python tính số lượng các phần tử không tăng nhiều nhất.

    Bài 33. Viết chương trình Python tìm vị trí bắt đầu đoạn con dương liên tiếp có nhiều phần tử nhất.

    Bài 34. Viết chương trình Python tìm đoạn con có các số hạng dương liên tiếp có tổng lớn nhất. (Nếu có nhiều đoạn con thoả mãn thì đưa ra màn hình: Số đoạn con thoả mãn và các đoạn con đó).

    Bài 35. Viết chương trình Python đếm số lượng các phần tử bằng giá trị x nhập từ bàn phím.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

x=float(input('Nhập 1 số từ bàn phím: '))
dem=0
for i in range(0,n):
    if a[i]==x:
        dem=dem+1
print('Số lượng phần tử bằng',x,':',dem)

    Bài 36. Viết chương trình Python chuyển các phần tử dương của danh sách lên đầu danh sách và in danh sách ra màn hình.

    Bài 37. Viết chương trình Python tìm số phần tử là dương và là số nguyên tố của danh sách và vị trí của nó trong danh sách.

    Bài 38. Viết chương trình Python chèn một số m (m nhập vào từ bàn phím ) vào đầu danh sách, cuối danh sách và vị trí thứ 5 của danh sách.

    Bài 39. Viết chương trình Python chèn danh sách [1,2,3] vào vị trí đầu, cuối và thứ 5 của danh sách.

    Bài 40. Viết chương trình Python xóa phần tử thứ k (k nhập từ bàn phím) trong danh sách.

    Bài 41. Viết chương trình Python sắp xếp danh sách theo thứ tự tăng dần, giảm dần.

    n=10
a=[2, -4, 1, 9, -3, 6, 3, -2, 6, 8]

x=float(input('Nhập 1 số từ bàn phím: '))
dem=0
for i in range(0,n):
    if a[i]==x:
        dem=dem+1
print('Số lượng phần tử bằng',x,':',dem)
#--------------------------------------------------------
# Bài 41. Sắp xếp danh sách tăng dần, giảm dần
#Sắp xếp danh sách tăng
for i in range(0,n-1):
   for j in range(i+1,n):
      if a[i]>a[j]:
         t=a[i]
         a[i]=a[j]
         a[j]=t
print('Danh sách đã sắp xếp tăng:')
print(a)
#Sắp xếp danh sách giảm
for i in range(0,n-1):
   for j in range(i+1,n):
      if a[i]<a[j]:
         t=a[i]
         a[i]=a[j]
         a[j]=t
print('Danh sách đã sắp xếp giảm:')
print(a)

    (Còn tiếp)

  • Sàng số nguyên tố (Sàng Eratosthenes)

    Sàng số nguyên tố (Sàng Eratosthenes)

    Sàng số nguyên tố (Sàng Eratosthenes)

    Bài toán liệt kê các số nguyên tố nhỏ hơn số n cho trước là một bài toán quan trọng trong Toán học và Tin học.

    Phương pháp đơn giản nhất là chúng ta duyệt qua các số tự nhiên nhỏ hơn n, và lần lượt kiểm tra tính nguyên tố của từng số này. Tuy nhiên, việc kiểm tra tính nguyên tố của một số tự nhiên n có độ phức tạp là $O(\sqrt{n})$, do đó duyệt qua n số này sẽ có độ phức tạp $O(\sqrt{1}+\sqrt{2}+\sqrt{3}+…+\sqrt{n})$.

    Cách làm dưới đây sẽ giúp giảm độ phức tạp của chương trình đi rất nhiều.

    Sàng Eratosthenes là gì?

    Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố nhỏ hơn 100. Thuật toán này do nhà toán học cổ Hy Lạp là Eratosthenes (Ơ-ra-tô-xten) “phát minh” ra.

    Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.

    Bạn có thể xem trong hình dưới đây, các số tô màu giống nhau là bội của nhau số cùng màu nhưng được tô đậm hơn.

    sàng số nguyên tố Sàng Eratosthenes

    Thuật toán sàng số nguyên tố

    Để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên N bằng sàng Eratosthenes, ta làm như sau:

    • Bước 1: Tạo 1 danh sách (List trong Python, Dart hoặc array trong C)các số tự nhiên liên tiếp từ 2 đến n: [2, 3, 4,..., n].
    • Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
    • Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,… sẽ bị đánh dấu vì không phải là số nguyên tố.
    • Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p và nhỏ hơn hoặc bằng căn bậc 2 của n . Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.

    Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.

    Thay vì phải đánh dấu, chúng ta có thể xóa phần tử không là số nguyên tố của danh sách thì cuối cùng sẽ còn lại là các số nguyên tố.

    Mời bạn tham khảo mã nguồn chương trình bằng Python:

    def SieveOfEratosthenes(n):
   
   # Create a boolean array "prime[0..n]" and initialize
   # all entries it as true. A value in prime[i] will
   # finally be false if i is Not a prime, else true.
   prime = [True for i in range(n + 1)]
   p = 2
   while (p * p <= n):
      
      # If prime[p] is not changed, then it is a prime
      if (prime[p] == True):
         
         # Update all multiples of p
         for i in range(p ** 2, n + 1, p):
            prime[i] = False
      p += 1
   prime[0]= False
   prime[1]= False
   # Print all prime numbers
   for p in range(n + 1):
      if prime[p]:
         print(p)
if __name__=='__main__':
   n = 30
   print("Following are the prime numbers smaller than or equal to", n)
   SieveOfEratosthenes(n)
  • Thuật toán kiểm tra Số Nguyên Tố

    Thuật toán kiểm tra Số Nguyên Tố

    Thuật toán kiểm tra Số Nguyên Tố

    Thuật toán kiểm tra Số Nguyên Tố của một số nguyên dương, cùng với thuật toán tìm UCLN của hai số tự nhiên là những bài toán quan trọng trong Lập trình.

    Kiểm tra tính nguyên tố là bài toán kiểm tra xem một số tự nhiên n có phải là số nguyên tố hay không. Bài toán này đặc biệt trở nên quan trọng khi các hệ mật mã khoá công khai ra đời.

    1. Số nguyên tố là gì?

    Số nguyên tố (prime) là số tự nhiên lớn hơn 1, chỉ có hai ước số là 1 và chính nó. Theo định nghĩa này thì các số 2, 3, 5, 7, 11,… là các số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất.

    số nguyên tố là gì

    Ví dụ: 7 là số nguyên tố vì trong khoảng từ 2 đến 6 không tồn tại số nào mà 7 chia hết cả.

    2. Các Thuật toán kiểm tra Số Nguyên Tố Đơn Giản

    Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m nằm trong khoảng 2 đến n-1 hay không.

    Nếu n chia hết cho một trong các số m nào đó thì n không là số nguyên tố (còn được gọi là hợp số composite). Ngược lại, nếu n không chia hết cho bất kì số m nào thì kết lianaj n là số nguyên tố.

    Thực ra việc kiểm tra với m từ 2 đến n-1 là không cần thiết, mà chỉ cần kiểm tra đến $\sqrt{n}$ là đủ. Vì nếu n là hợp số thì nó chắc chắn có ước số không vượt quá sqrt(n).

    Lặp từng phần tử với bước nhảy 1 đến n-1

    Giả sử cần kiểm tra số n có phải là số nguyên tố hay không thì các bước thực hiện như sau:

    • Bước 1: Nhập vào n
    • Bước 2: Kiểm tra nếu n < 2 thì kết luận n không phải là số nguyên tố
    • Bước 3: Lặp từ 2 tới (n-1), nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.

    Độ phức tạp của thuật toán trên là $O(n)$.

    Lặp từng phần tử với bước nhảy 2

    Theo định nghĩa thì số 2 là số nguyên tố chẵn duy nhất, vì vậy ta sẽ loại 2 ra khỏi vòng lặp và trong thân vòng lặp chỉ kiểm tra các số lẻ mà thôi, cách này sẽ tối ưu hơn cách 1 rất nhiều.

    • Bước 1: Nhập vào n;
    • Bước 2: Kiểm tra nếu n < 2 thì kết luận n không phải là số nguyên tố;
    • Bước 3: Kiểm tra nếu n = 2 thì kết luận n là số nguyên tố;
    • Bước 4: Kiểm tra nếu n > 2 và chẵn thì kết luận n không phải là số nguyên tố;
    • Bước 5. Lặp từ 3 tới (n-1), bước nhảy là 2 nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.

    Lặp từng phần tử đến $\sqrt{n}$

    Để tối ưu hơn, thay vì lặp tới n-1, chúng ta chỉ cần lặp các số từ 2 đến sqrt(n), nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.

    Độ phức tạp của thuật toán trên là $O(\sqrt{n})$.

    Xem mã nguồn viết bằng ngôn ngữ Dart tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-17.html

    3. Tối ưu thuật toán kiểm tra số nguyên tố

    Chúng ta có thể tối ưu thuật toán trên bằng cách chỉ ra n không chia hết cho những số nguyên tố nhỏ hơn nó. Tuy nhiên, chúng ta lại chưa biết được các số nguyên tố nhỏ hơn nó là những số nào (Bạn có thể sử dụng phương pháp sàng số nguyên tố – Sàng Eratosthenes để tìm ra các số nguyên tố nhỏ hơn số n cho trước). Nên ta sử dụng kết quả sau đây:

    Tất cả những số nguyên tố lớn hơn 3 đều có dạng 6k ± 1 (vì 6k, 6k ± 2, là những số chẵn; 6k + 3 thì chia hết cho 3).

    Do đó, chúng ta chỉ cần kiểm tra các số có dạng 6k ± 1 từ 2 đến √n, nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.

    def is_prime(n: int) -> bool:
    """Primality test using 6k+-1 optimization."""
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** 2 <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

    4. Các Thuật toán kiểm tra Số Nguyên Tố Nâng Cao

    Các cách kiểm tra số nguyên tố kể trên có độ chính xác tuyệt đối nhưng khối lượng tính toán rất lớn. Theo Wiki thì chúng ta còn có những cách khác để kiểm tra tính nguyên tố của một số với một độ chính xác cho trước.

    Kiểm tra theo xác suất

    Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên.

    Giả sử có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố p và một số tự nhiên a <= p. Nếu n là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một a<= n được lấy ngẫu nhiên, khi đó a có khả năng là một số nguyên tố.

    Ta đưa ra một thuật toán, kết luận rằng n là số nguyên tố. Nó là một thuật toán ngẫu nhiên hay thuật toán xác suất. Trong các thuật toán loại này, dùng một kiểm tra ngẫu nhiên sẽ không bao giờ kết luận một số nguyên tố là hợp số nhưng lại có thể kết luận một hợp số là số nguyên tố. Do đó, phương pháp này không chính xác một cách tuyệt đối.

    Xác suất sai của phép kiểm tra có thể giảm xuống nhờ việc chọn một dãy độc lập các số a; nếu với mỗi số a xác suất để thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau k lần thử độc lập, xác suất sai là nhỏ hơn 2^k, độ tin cậy của thuật toán sẽ tăng lên theo k.

    Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là:

    • Chọn một số ngẫu nhiên a.
    • Kiểm tra một hệ thức nào đó giữa số a và số n đã cho. Nếu hệ thức sai thì chắc chắn n là một hợp số (số a là “bằng chứng” chứng tỏ n là hợp số) và dừng thuật toán.
    • Nếu hệ thức đúng, chúng ta lặp lại hai bước trên cho đến khi đạt được một số lần định trước hoặc gặp trường hợp dừng thuật toán.

    Sau nhiều lần thử, nếu hệ thức đúng với nhiều giá trị của a, ta có thể nói rằng n “có khả năng cao” là số nguyên tố chứ không thể chắc chắn n là số nguyên tố. Tất nhiên là chúng ta sẽ tìm cách tăng “khả năng” này lên bằng cách thực hiện nhiều tính toán hơn.

    Các hệ thức thường sử dụng

    Nếu p là một số nguyên tố thì

    • 2p - 1 ≡ 1 (mod p) (đây là nội dung của định lí Fermat nhỏ)
    • fp + 1 ≡ 0 (mod p) (với fp + 1 là số Fibonacci thứ p + 1 và p có dạng 5k ± 2)
    • (p - 1)! ≡ -1 (mod p) khi và chỉ khi p nguyên tố. Đây là nội dung của định lí Wilson, nhưng việc tính toán biểu thức (n - 1)! % n sẽ có độ phức tạp lớn hơn log n.

    Các phép kiểm tra tính nguyên tố ngẫu nhiên là:

    • Phép kiểm tra tính nguyên tố của Fermat (kiểm tra Fermat). Đây là phép thử heuristic; tuy nhiên ít người sử dung phép thử này.
    • Kiểm tra Miller-Rabin và Kiểm tra Solovay-Strassen. Với mỗi hợp số n, ít nhất 3/4 (với kiểm tra Miller-Rabin) hoặc 1/2 (Với kiểm tra Solovay-Strassen) các số a là bằng chứng chứng tỏ n là hợp số).

    thuật toán kiểm tra số nguyên tố

    Các phép kiểm tra tất định

    Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Trên thực tế thuật toán này chạy chậm hơn các phương pháp xác suất.

    Các phương pháp này, mời bạn đọc tham khảo thêm tại https://en.wikipedia.org/wiki/Primality_test