Introduction

When it comes to checking whether a number is prime, the usual approach is to test it against 2, 5, 7, 11, 13, 17, and so on. But this method is only fairly reliable for numbers under 1000. I started wondering: is there a way to check for primes that is absolutely correct and doesn't rely on other Python modules? After all, with Python's math module, checking for primes becomes trivial, but importing a math module just for this feels a bit overkill.

The Conventional Algorithm

print("素数的概念是只可以被1和它本身整除的数字。\n欢迎来到这里，我们将在这里计算你所输入的数字是否为素数。")
while True:
    number = input("输入你的数字吧：")
    number = int(number)
    if number == 2:
        print("是素数")
    elif number == 3:
        print("是素数")
    elif number == 5:
        print("是素数")
    elif number == 7:
        print("是素数")
    elif number == 11:
        print("是素数")
    elif number == 17:
        print("是素数")
    elif number == 13:
        print("是素数")
    elif number == 19:
        print("是素数")
    else:
        if number % 2 == 0:
            print("\t此数可以被2整除，因此不是素数。")
        else:
            if number % 3 == 0:
                print("\t此数可以被3整除，因此不是素数。")
            else:
                if number % 5 == 0:
                    print("\t此数可以被5整除，因此不是素数。")
                else:
                    if number % 7 == 0:
                        print("\t此数可以被7整除，因此不是素数。")
                    else:
                        if number % 11 == 0:
                            print("\t此数可以被11整除，因此不是素数。")
                        else:
                            if number % 13 == 0:
                                print("\t此数可以被13整除，因此不是素数。")
                            else:
                                if number % 17 == 0:
                                    print("\t此数可以被17整除，因此不是素数。")
                                else:
                                    if number % 19 == 0:
                                        print("\t此数可以被19整除，因此不是素数。")
                                    else:
                                        print("是素数")

That's 46 lines of code in total, and it can determine whether a number is prime in a very short time. However, this algorithm is not accurate!

As shown in the figure, if we enter the number 5773, it can be divided by at least four numbers: 23, 251, 5773, and 1. But the algorithm says it's prime, so this algorithm is not accurate.

However, one advantage of this algorithm is that it can reach a conclusion very quickly, without consuming much CPU power.

The Advanced Algorithm

We know there is a method that is absolutely correct for checking primes.

When checking whether a number n is prime, we can divide n by every number from 1 to n and see if any of them divide evenly. If the count of divisors is greater than 2, it means there are numbers other than 1 and n itself that can divide it, which violates the definition of a prime number. In that case, n is not prime; otherwise, it is prime.

print("提示：最终结果的显示时间取决与CPU的算力和你输入的数大小\n建议输入一千万以下的数字，数字太大无法在短时间内得出结果")
x = int(input('输入一个数：'))
z = 0
for i in range(1,x+1):
    if x % i == 0:
        z = z+1
if z > 2:
    print("不是素数")
else:
    print("是素数")

This is an advanced algorithm that uses Python's built-in code and functions. The results it produces are 100% correct, but it has one drawback: because it uses a brute-force method, if the number is extremely large, we won't be able to get the result in a short time, and it requires a huge amount of CPU power to compute.

Building the Algorithmic Thinking

Conventional Algorithm

The figure only shows a simple thought process, but it can be extended by analogy. We can continue dividing by 7, 11, 13, 17, 23, and so on.

Advanced Algorithm

This is a nearly perfect method.

Code Analysis

Introduction

Since this code analysis heavily uses algorithms that have already been discussed, we will only analyze two built-in functions.

Using int() for Number Conversion

The int() function is used in the advanced algorithm. We nest int() with input() so we don't need an extra line of code for conversion. Its function is similar to float(), but it doesn't convert the number to a floating-point number; instead, it produces a solid integer.

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

A simple example can show you the difference between it and the float() function.

The output looks like this:

2
2
3

It doesn't have a decimal point or any digits after it.

Using range() to Generate Numbers

This is a very simple function. You can learn more about it at Python range() Function Usage | Runoob Tutorial.

Here, I'll just give a simple example:

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

The output:

1
2
3
4
5
6
7
8
9

Conclusion

Researching prime number algorithms is my first step into the world of algorithms, and I will keep improving from here!