소수를 찾는 에라토스테네스의 체 알고리즘

에라토스테네스의 체는 주어진 한계까지 소수를 찾는 데 사용되는 간단하고 오래된 알고리즘입니다. 작은 소수를 찾는 가장 효율적인 방법 중 하나입니다.

주어진 상한 n에 대해 알고리즘은 2부터 시작하여 소수의 배수를 합성으로 반복적으로 표시하여 작동합니다. 2의 모든 배수가 합성으로 표시되면 다음 소수의 배수, 즉 3이 합성으로 표시됩니다. 이 과정은 p*p ≤ n이 될 때까지 계속됩니다. 여기서 p는 현재 소수입니다.


다음은 소수를 찾는 에라토스테네스의 체 알고리즘입니다.

1. n 아래의 모든 소수를 찾으려면 2에서 n까지의 모든 정수 목록을 생성하십시오.


(참고: 1은 소수가 아닙니다)

2. 가장 작은 소수로 시작합니다. 즉, p = 2
3. n보다 작은 p의 모든 배수를 합성으로 표시하십시오. 이를 위해 숫자를 0으로 표시합니다. (p 자체를 합성으로 표시하지 마십시오.)
4. 목록에서 p보다 큰 다음 0이 아닌 숫자에 p의 값을 할당합니다.
5. p*p ≤ n이 될 때까지 과정을 반복합니다.

예: 11까지의 모든 소수 생성

가장 먼저 주목해야 할 점은 프라임 자체를 합성으로 표시하지 않는다는 것입니다.
1. 2에서 11 사이의 정수 목록을 만듭니다.


2
삼
4
5
6
7
8
9
10
11



2. p=2로 시작
3. 2*2 ≤ 11이므로 계속하십시오.
4. 목록에서 값을 0으로 설정하여 2의 모든 배수를 합성으로 표시합니다.


2
삼
0
5
0
7
0
9
0
11



5. p의 값을 다음 소수, 즉 3에 할당
6. 3*3 ≤ 11이므로 계속하십시오.
7. 목록에서 값을 0으로 설정하여 3의 모든 배수를 합성으로 표시합니다.


2
삼
0
5
0
7
0
0
0
11



8. p의 값을 5에 할당
9. 5*5 ≰ 11이므로 여기에서 멈춥니다.
우리는 끝났어! 목록은 다음과 같습니다.


2
삼
0
5
0
7
0
0
0
11



0인 모든 숫자는 합성수이므로 0이 아닌 모든 숫자는 소수입니다.

따라서 11까지의 소수는 2, 3, 5, 7, 11입니다.

에라토스테네스의 체를 사용하여 주어진 한계보다 작거나 같은 모든 소수를 인쇄하는 파이썬 프로그램.

n = int(input("Enter an integer number:"))
prime = [] # An empty list
for i in range(n+1):
    prime.append(i)

prime[0]=0
prime[1]=0   

p = 2
while (p * p <= n): 
    # If prime[p] is not changed, then it is a prime 
    if (p != 0): 
        # Update all multiples of p to zero
        for i in range(p*2, n+1, p): 
            prime[i] = 0

    p += 1

#print all element of list which are not zero
print("All the prime numbers up to", n, "are:")
for i in range(len(prime)):
    if (prime[i] != 0):
        print(prime[i], end=" ")

산출:
정수 입력:30
30까지의 모든 소수는 다음과 같습니다.
2 3 5 7 11 13 17 19 23 29