[알고리즘] 소수찾기 - 에라토스테네스의 체(C++ / Python)

소수를 구할 때 시간효율적으로 풀 수 있도록 주로 이 방법을 사용한다고 함.

 

소수 구하기

2 ~ N 까지 에라토스테네스 채를 통해 소수를 구하는 방법은 다음과 같다.

 

1. 2부터 시작해서 N까지 진행
2. 가장 작은 수를 선택
3. 그 작은 수를 소수라고 가정하고 작은 수부터 N까지 그 작은 수의 배수를 모두 제거

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

 

#include<stdio.h>
#include<cmath>
using namespace std;


int main(){
	int n = 1000;
	int check[1001] = { false };

	check[0] = check[1] = true;
	for (int i = 2; i < sqrt(1000); i++){
		if (check[i] == false){
			for (int j = i + i; j <= 1000; j += i){
				check[j] = true;
			}
		}
	}

	for (int i = 1; i <= n; i++){
		if (!check[i]) printf("%d ", i);
	}
	


	return 0;
}

 

[Reference]

   [1] Python

   [2] c++