Hướng dẫn how do you define a prime number in python? - làm thế nào để bạn xác định một số nguyên tố trong 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, 3Không
7 1, 2Đúng
15 1, 3Khô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 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ố.

Hướng dẫn how do you define a prime number in python? - làm thế nào để bạn xác định một số nguyên tố trong python?

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
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
  • 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 True

Khác, nếu a> b, thì a> √n và b <√n.

  • Vì vậy, thay vì lặp qua tất cả các số nguyên lên đến n/2, bạn có thể chọn chạy lên đến √n. Và điều này hiệu quả hơn rất nhiều so với cách tiếp cận trước đây của chúng tôi.
  • Cách sửa đổi thuật toán is_prime () thành o (√n)n may not be a perfect square, we’ll have to cast it into an integer. Use
    def is_prime(n):
      for i in range(2,n):
        if (n%i) == 0:
          return False
      return True
    2 to cast
    def is_prime(n):
      for i in range(2,n):
        if (n%i) == 0:
          return False
      return True
    3 into an
    def is_prime(n):
      for i in range(2,n):
        if (n%i) == 0:
          return False
      return True
    4.
  • Hãy để tiến hành tối ưu hóa chức năng để kiểm tra các số nguyên tố trong Python.

Bây giờ, hãy để phân tích định nghĩa hàm 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")
0

Để tính toán căn bậc hai của một số, hãy để mô-đun toán học tích hợp của Python, và sử dụng hàm

def is_prime(n):
  for i in range(2,n):
    if (n%i) == 0:
      return False
  return True
1.

Vì n có thể không phải là một hình vuông hoàn hảo, chúng tôi sẽ phải ném nó vào một số nguyên. Sử dụng def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return True2 để đúc def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return True3 vào def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return True4.

Để đảm bảo rằng chúng tôi thực sự kiểm tra tối đa √n, chúng tôi thêm một cộng với chức nă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 không bao gồm điểm cuối của phạm vi theo mặc đị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")
1

Ô 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.

  • 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)
  • 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.

Hướng dẫn how do you define a prime number in python? - làm thế nào để bạn xác định một số nguyên tố trong python?

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ố.
Hướng dẫn how do you define a prime number in python? - làm thế nào để bạn xác định một số nguyên tố trong python?

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 xác định một số nguyên tố trong Python?

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ừ 2 đến NUM - 1 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 True 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 cờ là đúng hay sai. Nếu đó là sự thật, Num không phải là số nguyên tố.

Làm thế nào để bạn đại diện cho các số nguyên tố trong Python?

Chương trình Python cho số nguyên tố khởi tạo một vòng lặp bắt đầu từ 2 kết thúc ở giá trị nguyên của sàn của căn bậc hai của số. Kiểm tra xem số có chia hết cho 2. Lặp lại cho đến khi căn bậc hai của số được kiểm tra không. Trong trường hợp, số là chia hết cho bất kỳ số nào, số không ...Initialize a for loop starting from 2 ending at the integer value of the floor of the square root of the number. Check if the number is divisible by 2. Repeat till the square root of the number is checked for. In case, the number is divisible by any of the numbers, the number is not ...

Làm thế nào để bạn xác định một số là số nguyên tố?

Một số nguyên tố là một số toàn bộ lớn hơn 1 yếu tố duy nhất là 1 và chính nó.Một yếu tố là một số toàn bộ có thể được chia đều thành một số khác.Một vài số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23 và 29.a whole number greater than 1 whose only factors are 1 and itself. A factor is a whole number that can be divided evenly into another number. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29.

Làm thế nào để bạn viết một hàm cho một số nguyên tố?

Liên kết trực tiếp đến câu trả lời này..
quet sạch tât cả;.
N = input ('số nguyên tố cho đến:') ;.
Nếu n
return;.
otherif n == 2 ..
return;.
cho i = 4: n ..
Nếu c == 1 ..