At Atcoder Biginner Contest170, I saw that the idea of Eratosthenes's sieve was applied, and I decided to write it because I didn't understand even Eratosthenes's sieve. This article is for understanding the principle rather than practicality, so if you arrived during the contest etc. here Is recommended. (This is the website of Mr. Takotsubo, who is always a reference.)
First, we use a technique called trial division. It is not a prime number because it divides in order by a number larger than 2, and if it is divisible, it has that number as a divisor. However, it is not necessary to divide by all numbers up to $ N $. If $ N $ has a divisor of $ d $, then $ N / d $ is also a divisor of $ N $, whichever is smaller. The smaller one is the largest when these two are equal, so it's enough to look up to $ \ sqrt {N} $ (the smaller one is removed and the larger one is already checked). From the above, this primality test can be calculated with $ O (\ sqrt {N}) $. Here, as a point of speeding up, if you have an even number as a divisor, it should be divisible by 2, so it seems that you should check only odd numbers after 2. (Not considered this time)
# O(√N)
def is_prime(n):
if n == 1:
return True
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
Next, let's look at a technique called eratosthenes sieving. This is the idea that all prime numbers under $ N $ will be listed, and if there are multiple targets to be judged, it will be possible to judge with $ O (1) $ after preprocessing. The disadvantage is that it requires an array of size $ N $, which increases the memory usage.
Now let's see how to create a prime number table. First, consider all numbers as candidates for prime numbers. Since 1 is not a prime number, I will delete it from the candidates. (For the convenience of the array, 0 is also included, but it is not a prime number, so it is implemented to delete it)
Next, look at the numbers from the smallest in order from 2, and if the number is a prime number, the multiple is the composite number. Therefore, all multiples will be deleted from the candidates. It seems to be called an Eratosthenes sieve because it seems to be sieved and dropped from the candidates in this way.
The amount of calculation is a little complicated, but I will give you some knowledge. The number of times that can be divided by each prime number is $ N / p $ times if the prime number is p, and if you write only the first number
# O(NloglogN)
def eratosthenes_sieve(n):
is_prime = [True]*(n + 1)
is_prime[0] = is_prime[1] = False
for p in range(2, n + 1):
if is_prime[p]:
for q in range(2*p, n + 1, p):
is_prime[q] = False
return is_prime
Since it is a prime number table to return, I will write how to use it for the time being.
n = 10
is_prime = eratosthenes_sieve(n)
print(is_prime[5]) # True
print(is_prime[10]) # False
・ HP of Takotsubo-san ・ [Programming Contest Challenge Book](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F % E3% 83% B3% E3% 82% B0% E3% 82% B3% E3% 83% B3% E3% 83% 86% E3% 82% B9% E3% 83% 88% E3% 83% 81% E3 % 83% A3% E3% 83% AC% E3% 83% B3% E3% 82% B8% E3% 83% 96% E3% 83% 83% E3% 82% AF-% E7% AC% AC2% E7% 89% 88-% EF% BD% 9E% E5% 95% 8F% E9% A1% 8C% E8% A7% A3% E6% B1% BA% E3% 81% AE% E3% 82% A2% E3% 83 % AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E6% B4% BB% E7% 94% A8% E5% 8A% 9B% E3% 81% A8 % E3% 82% B3% E3% 83% BC% E3% 83% 87% E3% 82% A3% E3% 83% B3% E3% 82% B0% E3% 83% 86% E3% 82% AF% E3 % 83% 8B% E3% 83% 83% E3% 82% AF% E3% 82% 92% E9% 8D% 9B% E3% 81% 88% E3% 82% 8B% EF% BD% 9E-% E7% A7% 8B% E8% 91% 89-% E6% 8B% 93% E5% 93% 89-ebook / dp / B00CY9256C)
Recommended Posts