소수 찾기 (에라토스테네스 체)및 빅 오 표기법

영카이브 2023. 12. 14. 21:12

문제 . 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

입력예시 : 30

답 : 10

나의 답변

import java.util.Scanner;
public class Main {
	public int solution(int n){
		int answer = n; 
		int no = 1; 
		for( int i=3; i<=n; i++) {
			for( int x=2; x<i; x++) {
				if(i%x==0) {
					no++; 
					break; 
				}
			}
		}
		answer= answer-no; 
		return answer; 
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(T.solution(n));
	}
}

오답 : Time Limit Exceeded

소수 찾기에선 에라토스테네스 체를 사용하는 것이 유용하다

에라토스테네스 체란?

2부터 시작해서 배수들을 지워나가면서 소수를 찾는 방식으로 2는 소수이므로 2의 배수들을 모두 제거한다.
다음으로 남아있는 가장 작은 수는 다음 소수이며, 그 배수들을 다시 제거한다. 이 과정을 반복하여 소수를 찾는다.
O(Nlog(log N)) 의 시간복잡도를 가진다.

ex) N이 100일 때
O(N log log N) : 약 514번의 연산
O(N^2) : 10,000번의 연산

정정 답변

import java.util.Scanner;
public class Main {
	public int solution(int n){
		int answer = 0;
		// 임의의 ck배열을 n+1 배열로 만드는건 인덱스번호를 자연수라고 여김
		int[] ck = new int[n+1];
		for( int i=2; i<=n; i++) {
			if( ck[i]==0 ) {
				answer++; 
				// i의 배수로 for문을 돈다.
				for( int x=i; x<=n; x=x+i) ck[x]=1; 
			}
		}
		return answer;
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.print(T.solution(n));
	}
}

시간 복잡도란?

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가

빅 오 표기법 이란?

시간 복잡도를 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용한 표현

실행속도 : O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(2^N)

O(1) : 가장 빠른 표기법, 데이터가 늘어나도 알고리즘 단계 수는 증가하지 않는다.
O(logN) : 데이터가 두 배로 증가할 때마다 알고리즘 단계가 한 단계씩 증가한다. 즉 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다. ex) 이진 검색
O(N) : 데이터가 늘어날 때 정확히 그 데이터에 비례해 알고리즘 단계 수가 증가한다.
O(NlogN) : logN번 반으로 나누고 나눌 때마다 모든 하위 데이터에 대해 분할을 수행하고 그 하위 데이터를 모두 합하면 N개 이다. ex) 퀵 정렬
O(N^2) : 데이터가 늘어날 때 n제곱만큼 단계 수가 걸린다. ex) 버블 / 선택 / 삽입 정렬
- 버블 정렬은 선택 정렬보다 두 배 느리다.
- 선택 정렬과 삽입 정렬은 경우에 따라 다르다.
O(2^N) : 가장 느린 표기법 ex) 피보나치 수열

느린 O(N^2)을 빠른 방법으로 대체할 수 있는지 생각해 보아야 한다!