Using Python to Find Prime Numbers

-
What's a prime number?

A prime number is a natural number that's only divisible by 1 and itself.

Also, a composite number is a natural number with positive factors other than 1 and itself. Thus, we can conclude that a prime number is not a composite number by the definitions.

There are many algorithms to find prime numbers. First, we will introduce the simplest way to find prime numbers.

Determining whether a number is prime or not is not really very different from determining whether a number is composite or not. To determine whether a number is composite, it is by definition sufficient to find a factor other than 1 and itself. If we find such a factor m for a number n, i.e. m divides n, then we must have m < n. So we only need to find a factor of n in the range from 2 to n-1.

Here is the code:


However, this brute force algorithm will take a lot of time to find the prime numbers if the range is too large.

There is a better algorithm to save the time.

In ancient Greece, a mathematician called Eratosthenes proposed a method called the Eratosthenes sieve method. The Eratosthenes sieve method is a very classical algorithm for determining prime numbers and can be found in most of the various determinations of prime numbers that require exact solutions. Here I must repeat the long and fatal name of Eratosthenes many times to express my great respect for the great sage Eratosthenes. The ideas of the Eratosthenes sieve can be very illuminating, and the Eratosthenes sieve guides us in further narrowing the search for factors.

To do this, we need a more complex number theory derivation.

For a composite number n, we can show that it must have a non-trivial factor less than or equal to sqrt(n). A non-trivial factor here is a factor other than 1 and itself. If not, then all of its non-trivial factors are greater than sqrt(n). If we take any one of the non-trivial factors m which is different from n, then there exists an integer k such that n = km, then k is also a non-trivial factor of n, but k = n/m < sqrt(n), which is a contradiction, so the composite number n must have a non-trivial factor less than or equal to sqrt(n).

Thus, we only need to find the factors between 2 and [sqrt(n)], where [x] denotes floor function.

Note: [x] is the largest integer that is not greater than x.

Therefore, we can optimize our code to:


We can see that the effectiveness of the algorithm increases significantly.

However, it can still be optimized.

Since even numbers are divisible by 2, even numbers greater than 2 are not prime. Also, prime numbers greater than 2 are odd, so they don't have even factors. Therefore, we have:


Furthermore, we have a better algorithm which uses modulo 6.

Since any integer n modulo 6 is always between 0 and 5 inclusive, and we note that 6n, 6n+2, 6n+3, 6n+4 are not prime for all n greater than 0, so the positive integers that can be written in the form 6n+1 or 6n+5 are probably prime, i.e. the positive integers modulo 6 equal to 1 or 5 are probably prime. Also, we note that if the positive integers are not prime, then they will have a factor of the form 6k+1 or 6k+5, where k is a positive integer.

Therefore, we have:


Compared to the brute force algorithm, we can see that this algorithm is very fast at finding the prime numbers in a range. It only takes about 3 seconds to find all the prime numbers from 2 to 1000000, which is really amazing!

If you would like to test this algorithm, you can go to my web application and try it out for yourself:


You can also refer to the source code of my web application:

Comments

Post a Comment

Popular posts from this blog

How to Predict Stock Prices with a Multilayer Perceptron (MLP) Neural Network

-
Image
Predicting stock prices is one of the simple applications of AI in finance. Here I'm using Keras, which is a high-level deep learning API in TensorFlow. I have attempted to predict the future stock price of Padini, a fashion company in Malaysia, and the following graph shows the results of my prediction: It's tiring to train an AI, since you need to test the model with different parameters and settings. I have spent a few hours to adjust the model and find its best settings. It really requires a good intuition. But when you done it, you will feel excited! Disclaimer: This AI model's prediction results are not completely accurate, please do not invest according to the prediction results, otherwise you would lose money and I will not be responsible. Here I will explain the mathematical algorithms behind the MLP Model and provide the Python code in Jupyter to train the AI. Model Updated: The number of neurons in the input layer is reduced to 150. Also, the number of hidden lay...
Read more

AI Explained: The Most Common Questions and Answers for Newbies

-
As a self-taught AI learner, I have been studying AI for a while and I would like to share my experience of learning AI to help others who are interested in learning AI. Here I have summarized some common questions to help answer those who are interested in AI and want to learn AI. Also, i f I think of more questions in the future, I will update this article. Q1: Is mathematics necessary for learning AI? Can I just skip mathematics and dive right in to learn AI? A1: It's not recommended that you skip mathematics when learning AI, otherwise you will have no idea what you’re doing. That is not a good way to learn AI. In fact, mathematics is the core of AI, and AI is actually a complex mathematical model. Almost all the AI courses will require you to learn mathematics first, especially vector calculus, linear algebra, and advanced statistics. As I said earlier, AI = Coding + Math, and they cannot be separated. The best way to learn AI is to know how it works. Q2: I have heard about ma...
Read more

The Role of Mathematics in Artificial Intelligence

-
Image
Many people think that AI is only about coding, but mathematics is actually a fundamental part of AI. AI = Math + Coding, and they are both essential. AI is impossible without math or coding. However, training AI does not necessarily require a lot of mathematical knowledge. Most people train AI without fully understanding the mathematical algorithms behind it. But it is better if you know how AI works with mathematical algorithms. In fact, AI is based on a mathematical model. Some mathematical functions and algorithms are used in the model. It sounds abstract, but you can basically imagine it as using calculus to optimize something. So, how do we train an AI? First, we use advanced mathematics to model an AI, then we use coding to train the AI because the process of training AI is tedious, so we let our computer handle all the training stuff. That is why learning mathematics can help you understand AI more deeply, not just coding. Linear algebra, vector calculus, and advanced statistic...
Read more