Check the number of prime numbers less than or equal to n

What is a prime number (the beginning is a chat)

A prime number is an integer that is ** 2 or more and has only obvious divisors **. The trivial thing here refers to 1 and yourself. In other words, n is called a prime number when there are only 1 and n in which n ÷ m is an integer for an integer n.

Why prime numbers are important

That's because when you give the operation of product to a set of positive integers, the prime number is the ** base **. Anyone who has studied mathematics will understand how important the basis is. By the way, if the operation is sum, one basis is enough (only 1 can make all positive integers)

(By the way, in the old days when the concept of the basis was not maintained, it seems that prime numbers were not so important. It was recognized that there are such numbers.)

How many prime numbers are there?

Professor Euclid proved that the number of prime numbers is infinite long ago. In an era when there was no concept of infinity, he wrote in the phrase, "If the number of prime numbers is a number, there are more prime numbers than that." Nowadays, the convenient concept of infinity is in place, but who was Euclid who intuitively understood the concept of infinity so accurately when it wasn't there?

About the distribution of prime numbers

It turns out that the total number of prime numbers is infinite. But how many prime numbers are there in numbers from 1 to n? Was solved in 1896 with a rather difficult problem. (Now there is elementary lighting, but it's just elementary and it's quite difficult to understand.) Moreover, it is just a "ratio" and the exact formula "how many" is still unknown (probably). However, if you give n specifically, you can count humans and dogs with tremendous comprehension. Because you just have to divide by all the numbers less than or equal to n and make sure that only the divisors are trivial. You can do it if you do your best. And it seems that there was something like a prime number table in the 1800s. I don't know the upper limit of the number of prime numbers on board. However, it seems that there are quite a few mistakes, and Professor Euler proved in 1797 the theorem that ** 1000009 is not a prime number **. In other words, "whether or not n is a prime number can be calculated theoretically if you do your best, but it is a mistake." Then you can calculate what to do with a computer instead.

This time, the goal is not a program that determines whether n is a prime number, but a program that finds how many prime numbers are between ** 1 and n **.

Proposal 1.1 Let's break it anyway

The definition that n is a prime number is that there is nothing divisible by an integer from ** 2 to n-1 **. Then implement it programmatically

def number1(n):
    cnt=1
    for i in range(2,n+1):
        for j in range(2,i):
            if i%j==0:
                break
            elif i%j!=0 and j==i-1:
                cnt+=1
    return cnt

Since the process of 2 did not go well, I set cnt = 1 in advance, but I think that it will look like this if implemented obediently. Even this is overwhelmingly faster than humans, but at least I want to do Euler's up to 1000009 at explosive speed. This is too late. Let's think about improvement plans

Proposal 1.2 Let's think only odd numbers

When considering whether it is a prime number, even numbers other than 2 are obviously not prime numbers, right? If so, let's exclude it.

def number2(n):
    cnt=1
    for i in range(3,n+1,2):#← Only this has changed
        for j in range(2,i):
            if i%j==0:
                break
            elif i%j!=0 and j==i-1:
                cnt+=1
    return cnt

Now you only have to think about odd numbers! The number of calculations has simply been halved! Just one more thing here ... If the number to be divided is only an odd number, isn't it possible to divide only an odd number? ......

Proposal 1.3 Further odd numbers

def number3(n):
    cnt=2#change point
    for i in range(3,n+1,2):
        for j in range(3,i,2):#change point
            if i%j==0:
                break
            elif i%j!=0 and j==i-2:#change point
                cnt+=1
    return cnt

With this, all the numbers to be divided and the number to be divided except 2 are odd numbers! The number of calculations is simply 0.25 times! However, it is still late. I get angry with DI ○. Let's think about whether there is waste

Proposal 2.1 Let's divide by a prime number!

For example, if n did not break at 5, would it break at 25? The answer is no. If n ÷ 25 = integer It will be n ÷ 5 = 5 * integer. In other words, it's a waste of time, such as dividing by 9 even though it didn't divide by 3, or dividing by 15 even though it didn't divide by 3 and 5. In other words, ** only prime numbers are required to divide ** However, there is no point in using a list of prime numbers when you want to find a prime number, so let's make a list of prime numbers yourself. First reconfirm the definition I thought that there is no such thing as a prime number when n is divided by a number from 2 to n-1 to become an integer. Let's think that ** n is not divisible by any prime number less than n **! The definition is the same for both, but if you write it programmatically, it will change a lot! If you write a program with the idea that the number that can be divided is only an odd number

def number4(n):
    li=[2]
    for i in range(3,n+1,2):
        for j in li:
            if i%j==0:
                break
            elif i%j!=0 and j==li[-1]:
                li.append(i)
    return len(li)

I think it will be! It's much faster than it was at the beginning! There is still obvious waste.

Proposal 2.2 Let's divide by range

You are currently checking whether n ÷ prime number is an integer. What is the minimum value of this "integer"? ...... ** 2 **, right? In other words, if n is 100 or something, you don't have to divide it by 53 ...? Because obviously 100 ÷ 53 is less than 2. Then you can use this to save even more waste.

def number5(n):
    li=[2]
    for i in range(3,n+1,2):
        for j in li:
            if i%j==0:
                break
            elif i%j!=0 and 2*j>i:#change point
                li.append(i)
                break             #change point
   return len(li)

But you can still reduce the range!

Proposal 2.3 Consider the nature of numbers

Suppose n is not divisible by all ** prime numbers less than or equal to √n (this ** all ** assumption is very important) At this time, is n divided by a prime number larger than √n?

Actually, it's impossible.

If n ÷ m (prime number larger than √n) = k (integer) n ÷ k = m holds, right? But considering the nature of √ m> k (Because if m <k, you can write k = m + a n = m * (m + a) = m ^ 2 + m * a and the equality is buggy) Even though I assumed that it would not be divided by all prime numbers less than √n, it would be divided by such k. Proposal 2.2 was supposed to be considered in the range of prime numbers from 1 to n ÷ 2. Actually, it was good to have a prime number less than 1 ~ √n! Then let's implement this

def number6(n):
    li=[2,3]
    cnt=2
    for i in range(5,n+1,2):
        for j in li:
            if i%j==0:
                break
            elif i%j!=0 and j**2>=i:#change point
                cnt+=1
                li.append(i)
                break
    return cnt

This is pretty fast. This should be enough for play, and with this, only the knowledge of the number of prime numbers can beat Euler (maybe).

Let's aim for a little more speed

Proposal 3.1 Sieve

It was mentioned in my math textbook when I was in junior high school, but there is a way to find a prime number called ** Eratosthenes Sieve **. First, write the numbers 2,3,4,5,6, ..., n

  1. Circle the one at the beginning ②,3,4,5,6,...,n
  2. Erase all multiples of the numbers marked with 〇 ②, 3,5,7,9,11,...,n
  3. Ignore 〇 and add 〇 to the first number ②,③,5,7,9,11,...,n
  4. Erase multiples of the numbers marked with 〇 It's an algorithm that repeats that, and the numbers marked with 〇 are prime numbers less than or equal to n!

Let's implement this programmatically! Is the idea

I wonder if it will be as follows if I write it obediently

def number7(n):
    li=[int(x) for x in range(2,n+1)]
    pri=[]
    for i in range(n):
        pri.append(li[0])
        li=[int(x) for x in li if x%pri[-1]!=0]
        if len(li)==0:
            break
    return len(pri)

But this is pretty slow. Just what you thought above will come to life! It corresponds to the part of writing numbers first

    li=[int(x) for x in range(2,n+1)]

Part of. You don't have to write it from the beginning because you know that even numbers disappear first. Let's do this

def number8(n):
    li=[int(x) for x in range(3,n+1,2)]#change point
    pri=[2]#change point
    for i in range(n):
        pri.append(li[0])
        li=[int(x) for x in li if x%pri[-1]!=0]
        if len(li)==0:
            break
    return len(pri)

However, this is still quite slow. Because In the second half, the sieve is already finished. I think with n = 100 Erase multiples of 3,5,7. Actually, at this point, ** all prime numbers less than 100 are out ** It's the same as the previous story. ** Prime numbers less than √n are enough ** But the computer checks the sieve to the last prime number 97, and all the numbers in the list are multiples of 11, 13 or 17, 17 ..., 97? I'm sure. This useless process is slowing down. So let's add a process that ** √n is enough **

def number9(n):
    li=[int(x) for x in range(3,n+1,2)]
    pri=[2]
    for i in range(n):
        if pri[-1]**2>n:   #Changes around here
            pri+=li
            break
        else:
            pri.append(li[0])
            li=[int(x) for x in li if x%pri[-1]!=0]
        if len(li)==0:
            break
    return len(pri)

This is pretty fast! Compete with the previous program!

Speed check

This time, we will measure the speed only with number6 and number9! Respect Euler's 1000009 and calculate 10 times with n = 1,000,000 and calculate the average.

number6 :Average time 5.729981923103333
number9 :Average time 3.960706377029419

Sieve is fast (time varies depending on pc specifications, so it is for reference only)

the end

I tried to summarize how to find the number of basic prime numbers. I hope it helps> <

On a different note, I haven't been able to study the program recently because of a major university event () called test study. I would like to devote myself to improving my skills during this summer vacation, so I would appreciate your guidance and encouragement!

Recommended Posts

Check the number of prime numbers less than or equal to n
How to check the version of Django
Command to check the total number of CPU physical cores / logical cores / physical memory on Mac
Easy way to check the source of Python modules
python beginners tried to predict the number of criminals
How to know the port number of the xinetd service
How to get the number of digits in Python
Try to estimate the number of likes on Twitter
Discrimination of prime numbers
How to specify an infinite number of tolerances in the numeric argument validation check of argparse
How to find the optimal number of clusters in k-means
I made a function to check the model of DCGAN
Try to improve the accuracy of Twitter like number estimation
How to increase the number of machine learning dataset images
Commands and files to check the version of CentOS Linux
Is there a secret to the frequency of pi numbers?
10. Counting the number of lines
Get the number of digits
Calculate the number of changes
How to check the memory size of a variable in Python
Try to solve the N Queens problem with SA of PyQUBO
I tried to create a list of prime numbers with python
How to check the memory size of a dictionary in Python
[TensorFlow 2] How to check the contents of Tensor in graph mode
The first artificial intelligence. How to check the version of Tensorflow installed.
A command to easily check the speed of the network on the console
A script that returns 0, 1 attached to the first Python prime number
I want to check the position of my face with OpenCV!
I used the worldcup command to check the outcome of the World Cup.