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.
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.)
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?
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 **.
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
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? ......
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
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.
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!
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
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
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!
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)
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!