[Java] 소수 찾기

문제

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

 

풀이

에라토스테네스의 체를 참고했다.

https://ko.wikipedia.org/wiki/에라토스테네스의_체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        boolean[] primes = new boolean[n+1];
        //2~n
        for(int i=2;i<=n; i++)
            primes[i] = true;
        
        // 2 ~ i*i <= n
        // 각 배수 제거
        for(int i=2; (i*i)<=n; i++){
            if(primes[i]){
                for(int j=i*i; j<=n; j+=i){
                    primes[j] = false;
                    //i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화
                }
            }
        }
        
        for(int i=0; i<=n ; i++){
            if(primes[i])
                answer++;
        }
        
        return answer;
    }
}

 

www.youtube.com/watch?v=5ypkoEgFdH8

 

시간복잡도 O(N^(1/2))

→ 8의 경우 2 * 4 = 4 * 2와 같은 식으로 대칭을 이루기 때문에, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증해도 된다.

 

 

해당 숫자가 소수인지 판별하는 코드 (C)

bool isPrimeNumber(int x){
    int end = (int)sqrt(x);
    for(int i=2; i<=end; i++){
    	if(x%i==0) return false;
    }
    return true;
}

 

대량의 소수를 한꺼번에 판별하는 코드 (C)

int number = 100000; //10만개의 숫자
int a[100001];

void primenumberSieve(){
	for(int i=2; i<=number; i++){
    	a[i] = i;
    }
    
    for(int i=2; i<=number; i++){
    	if(a[i]==0) continue;
        for(int j=i+i; j<=number ; j++){
        	a[j] = 0;
        }
    }
    for(int i=2; i<=number ; i++){
    	if(a[i]!=0) printf("%d", a[i]);
    }
}