Python Learning Diary – Prime Number Judgment

Preface#

For determining whether a number is prime, the conventional method is to test with 2, 5, 7, 11, 13, and 17. However, this method only has a high accuracy rate for numbers below 1000. It makes one wonder if there is an absolutely correct method to determine prime numbers without using other Python modules. After all, with the Python math module, determining prime numbers becomes quite simple, but introducing a math module seems a bit excessive.

Conventional Algorithm#

print("The concept of a prime number is a number that can only be divided by 1 and itself.\nWelcome here, we will calculate whether the number you input is prime.")
while True:
    number = input("Please enter your number: ")
    number = int(number)
    if number == 2:
        print("It is a prime number")
    elif number == 3:
        print("It is a prime number")
    elif number == 5:
        print("It is a prime number")
    elif number == 7:
        print("It is a prime number")
    elif number == 11:
        print("It is a prime number")
    elif number == 17:
        print("It is a prime number")
    elif number == 13:
        print("It is a prime number")
    elif number == 19:
        print("It is a prime number")
    else:
        if number % 2 == 0:
            print("\tThis number can be divided by 2, so it is not a prime number.")
        else:
            if number % 3 == 0:
                print("\tThis number can be divided by 3, so it is not a prime number.")
            else:
                if number % 5 == 0:
                    print("\tThis number can be divided by 5, so it is not a prime number.")
                else:
                    if number % 7 == 0:
                        print("\tThis number can be divided by 7, so it is not a prime number.")
                    else:
                        if number % 11 == 0:
                            print("\tThis number can be divided by 11, so it is not a prime number.")
                        else:
                            if number % 13 == 0:
                                print("\tThis number can be divided by 13, so it is not a prime number.")
                            else:
                                if number % 17 == 0:
                                    print("\tThis number can be divided by 17, so it is not a prime number.")
                                else:
                                    if number % 19 == 0:
                                        print("\tThis number can be divided by 19, so it is not a prime number.")
                                    else:
                                        print("It is a prime number")

A total of 46 lines of code can determine whether a number is prime in a very short time, but this algorithm is not accurate!

As shown in the image, when we input the number 5773, it can be divided by at least 23, 251, 5773, and 1, but the algorithm indicates that it is a prime number, so this algorithm is inaccurate.

However, this algorithm has the advantage of quickly reaching a conclusion without consuming much CPU power.

Advanced Algorithm#

We know there is a method to determine prime numbers absolutely.

When determining whether a number n is prime, we can check all numbers from 1 to n to see if they can divide n. If the number of times it can be divided is greater than 2, it means there are other numbers besides 1 and n itself that can divide it, which contradicts the concept of a prime number, indicating that n is not prime; conversely, it is prime.

print("Tip: The display time of the final result depends on the CPU's computing power and the size of the number you input.\nIt is recommended to input a number below ten million, as larger numbers may not yield results in a short time.")
x = int(input('Enter a number: '))
z = 0
for i in range(1,x+1):
    if x % i == 0:
        z = z+1
if z > 2:
    print("It is not a prime number")
else:
    print("It is a prime number")

This is an advanced algorithm that utilizes Python's built-in code and functions to achieve its work, and the results it calculates are 100% accurate. However, it has one unique drawback: because it uses an exhaustive method, if the number is extremely large, we cannot obtain results in a short time and need to consume significant CPU power to compute.

Algorithmic Thinking Construction#

Conventional Algorithm

The diagram only shows a simple thought process, which can be extended further by continuing to divide by 7, 11, 13, 17, 23, and so on.

Advanced Algorithm

This is an almost perfect method.

Code Analysis#

Preface#

This code analysis focuses on two built-in functions due to the extensive use of previously discussed algorithms.

Using `int()` for Number Conversion#

The int() function is used in the advanced algorithm. We use int() nested within input(), eliminating the need to write an additional line of code for conversion. Its function is similar to that of the float() function, but it does not convert numbers to floating-point; instead, it produces a concrete integer.

a = "2"
b = int(a)
print(b)
c = b+1
print(b)
print(c)

A simple example illustrates the difference between it and the float() function.

The output is as follows:

2
2
3

It does not include decimal points or numbers after the decimal point.

Using `range()` to Generate Numbers#

A very simple function, which can be learned in detail at Python range() function usage | Runoob.

Here, I will provide a simple example:

for a in range(1,10):
    print(a)

The output is:

Conclusion#

The study of prime number algorithms is the first step I took in algorithm research, and I will gradually improve in the future!

This article is synchronized and updated by Mix Space to xLog. The original link is https://fmcf.cc/posts/technology/Python_Notes_5