[Algorithm] 에라토스테네스의 체를 통해 소수구하기

소수를 구할 때 가장 빠른 시간에 구할 수 있는 에라토스테네스의 체의 방법을 알아보자


환경 및 선수조건

  • C++


에라토스테네스의 체

2부터 n까지의 소수를 구할 때 에라토스테네스의 체를 이용한 방법은 아래와 같다.

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


  • 시간복잡도 : O(n*log(log(n)))


코드

  • count : 저장된 소수의 개수
  • c[n+1] : 2 ~ n까지 수에서 제거된 숫자를 체크하는 배열, true(제거됨), false(제거되지않음)
  • p[n] : 소수를 저장하는 배열

example.cpp

bool c[1000001]= {false,};
int p[1000000];
int count = 0;

//0~1000000까지 소수 구하기
for(int i=2; i<=1000000; i++){
	if(c[i] == false){
		// 추가
		p[count++] = i;
		// i의 배수 지우기
		for(int j=i+i; j<=1000000; j+=i){
			c[j]=true;
		}
	}
}


참고자료

  • 코드플러스 알고리즘 기초 강의

[Linux] 쉘 스크립트에서 멀티프로세스(혹은 스레드) 기능 사용하기

> 백그라운드로 명령어를 실행해서 병렬적으로 실행되는 멀티 프로세스 환경을 만들어보자.## 환경- Linux 기반 시스템- Bash shell(/bin/bash)## 멀티프로세스? 병렬처리? 멀티스레드? 백그라운드 프로세스?- 여기서 진행할 방식...… Continue reading