소수 판별 알고리즘

소수(Prime Number)

• 1과 자기 자신 외에는 나누어 떨어지는 정수가 없는 양의 정수

 

소수 판별법

• 2~N-1까지의 정수로 나누어 보는 방법 - O(N)
• 2~ sqrt(N)까지의 정수로 나누어 보는 방법 - O(N^(1/2))
• -> 12 = 2*6 = 3*4 = 4*3 = 6*2

 

코드 구현하기

int get_prime(int n){

    for(int i=2; i<n; i++){
    	
        if(n % i == 0) return false;
    }
    return true;
}

int get_prime2(int n){

    int sqrn;
    sqrn = (int)sqrt(n);
    for(int i=0; i<=sqrn; i++){
    	if(n % i == 0) return false;
    }
    return true;
}

 

에라토스테네스의 체

주어진 정수 N보다 작은 모든 소수를 구한다.

 

코드 구현하기

int main(){

    int n;
    cin >> n;
    int *parray;
    parray = new int[n+1]; // 메모리 할당
    
    int j;
    for(int i=2; i<=n; i++){
    	if(parray[i] == 1) continue; // 이미 지워진 수가 아니면 다음 수로 넘어간다.
        j = i;
        while((j+=i) <= n) {
        	parray[j] = 1; // i의 배수들은 소수가 아니라고 마킹한다.
        }
    }
    
   for(int i=2; i<=n; i++){
       if(parray[i] == 0) cout << "i "; 
    }
    delete [] parray;
}