Hướng dẫn check prime numbers in list python - kiểm tra số nguyên tố trong danh sách python

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 407

  1 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 407

  1 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 407

5 hoặc

407 is not a prime number
11 times 37 is 407

6. 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 407

7 để 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 407

9 để kiểm tra xem

407 is not a prime number
11 times 37 is 407

1 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 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ì 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ông

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.

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

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

7 trong Python.

Trong Python,

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

8 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ừ

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

9 cho đến

Prime numbers between 900 and 1000 are:
907
911
919
929
937
941
947
953
967
971
977
983
991
997

0 trong các bước của

Prime numbers between 900 and 1000 are:
907
911
919
929
937
941
947
953
967
971
977
983
991
997

1.

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 True

Bâ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]
# True

Trong đầ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 True

Hã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]
# 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ố.

import math
def is_prime[n]:
  for i in range[2,int[math.sqrt[n]]+1]:
    if [n%i] == 0:
      return False
  return True

Khác, nếu a> b, thì a> √n và b 1: for i in range[2, num]: if [num % i] == 0: break else: print[num]7 không bao gồm điểm cuối của phạm vi theo mặc định.

Ô mã bên dưới xác minh rằng chức năng của chúng tôi

Prime numbers between 900 and 1000 are:
907
911
919
929
937
941
947
953
967
971
977
983
991
997

4 hoạt động chính xá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"]

0

Trong phần tiếp theo, chúng ta hãy tạo một vài lô đơn giản để hiểu trực quan O [N] và O [√n].

So sánh trực quan O [N] và O [√n]

▶ Chạy đoạn mã sau trong môi trường Notebook Jupyter mà bạn chọ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"]

1

Đoạn trích trên cho thấy cách bạn có thể vẽ đường cong cho n và √n cho một loạt các giá trị.

• Chúng tôi sử dụng hàm arange [] numpy để tạo một mảng số.
• Và sau đó, chúng tôi thu thập các giá trị của N và √n lên đến, nhưng không bao gồm 20, vào khung dữ liệu gấu trúc.
• Tiếp theo, chúng tôi âm mưu sử dụng chức năng lineplot [] của Seaborn.

Từ cốt truyện dưới đây, chúng ta thấy rằng √n nhỏ hơn đáng kể so với n.

Bây giờ chúng ta hãy tăng phạm vi lên tới 2000 và lặp lại các bước tương tự như 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"]

2 Từ biểu đồ trên, bạn có thể suy ra rằng thuật toán O [√n] nhanh hơn đáng kể khi bạn kiểm tra nếu một số lượng lớn là số nguyên tố.

From the above plot, you can infer that O[√n] algorithm is significantly faster when you’re testing if a large number is prime.

Ở đây, một ví dụ nhanh: 2377 là một số nguyên tố, xác định điều này! 😀

Trong khi phương pháp O [n] sẽ thực hiện thứ tự 2000 bước, thuật toán O [√n] có thể giúp đi đến câu trả lời chỉ trong 49 bước.✅

Sự kết luận

Và đó là thời gian cho một bản tóm tắt nhanh chóng.

• Để kiểm tra xem một số là số nguyên tố, cách tiếp cận ngây thơ là lặp qua tất cả các số trong phạm vi [2, n-1]. Nếu bạn không tìm thấy một yếu tố phân chia N, thì N là số nguyên tố.
• Vì yếu tố duy nhất của N lớn hơn N/2 là chính N, bạn có thể chọn chỉ chạy lên đến N/2.
• Cả hai phương pháp trên đều có độ phức tạp về thời gian của O [N].
• Khi các yếu tố của một số xảy ra theo cặp, bạn chỉ có thể chạy đến √n. Thuật toán này nhanh hơn rất nhiều so với O [n]. Và mức tăng là đáng kể khi kiểm tra xem một số lượng lớn có phải là số nguyên tố hay không.

Tôi hy vọng bạn hiểu làm thế nào để kiểm tra xem một số là chính trong Python. Bước tiếp theo, bạn có thể kiểm tra hướng dẫn của chúng tôi về các chương trình Python về các hoạt động chuỗi, nơi bạn sẽ học cách kiểm tra xem các chuỗi có phải là palindromes, anagram và hơn thế nữa không.

Hẹn gặp lại tất cả các bạn trong một hướng dẫn khác. Cho đến lúc đó, mã hóa hạnh phúc! 👩🏽‍💻

Làm thế nào để bạn tìm thấy một danh sách các số nguyên tố?

Làm cách nào để lập danh sách các số nguyên tố trong Python?

Có chức năng isprime trong Python?

Làm thế nào để bạn tìm thấy một số nguyên tố trong một mảng trong Python?