소수 판별하기, 범위 내 소수 구하기

저번에 간단하게 올렸었지만 코드로는 이해 못해서 버벅거리니

하나하나 꼼꼼히 다시 정리하려한다

 

특정한 수의 소수 판별 함수

---

소수는 자기 자신과 1이외의 수로 나누어 떨어지지 않아야 하므로( 자신과 1 외에 약수가 없어야 하므로)

소수 판별 함수를 간단히 코드로 구현하면 아래와 같다

bool isPrimeNumber(int a){
	// 0은 물론이고, 1과 자기자신외의 숫자로 자신이 나눠져 떨어지는지 보므로 범위는 2이상, n 미만이다
	for(int i=2; i<n; i++){
    	// 1과 자기자신 외의 숫자 i 로 나누어 떨어지므로 소수가 아니다. false
    	if(a%i==0) return false;
    }
    // 2부터 자기 미만의 숫자들 i 중에 나누어 떨어지는 경우가 없었다면 소수가 맞다 true
    return true;
}

위의 식은 모든 경우의 수를 다 돌며 확인하므로 시간복잡도가 O(N)이 되어 비효율적이고 처리 속도가 느리다

때문에 이를 보완한 효과적인 생각이, 모든 수가 다 약수인지 나눠볼필요는 없다는 것이다.

12를 예로 들면 12는 3*4 와 4*3 과 같이 약수들이 대칭을 이루는데, 모든 숫자도 마찬가지다

이 원리를 이용하여 n개를 전부 확인할 필요없이 n 의 제곱근까지만 약수인지(나누어 떨어지는지) 확인하면 된다

12를 예로 들면 √12  이하의 숫자까지만 나누어 떨어지는지 돌며 계산해도 전체를 다 돈 경우와 같다는 말이다

 √12는 3.xx 이므로 확인하는 수 12를 2부터  √12 이하인 3까지만 나누어떨어지나 확인해도 소수 판별이 된다는 것이다

n의 제곱근만큼만 확인하면 되므로 시간 복잡도는 O(N) 이 되어 훨씬 빠르게 처리가 가능하다

#include <bits/stdc++.h>
using namespace std;

bool isPrimeNumber(int a){
	// 제곱근 이하까지만 나누어 떨어지나 확인하므로 a의 제곱근을 내림한 정수를 end라 한다
	int end = (int) sqrt(x);
	// 2부터 제곱근까지만 나누어 떨어지나 확인하여도 소수 판단은 성립한다
    for(int i = 2; i < sqrt(end); i++){
    // a가 2와 제곱근 사이의 수로 나누어 떨어진다면 a는 소수가 아니다 false 
    	if(a%i==0)
        	return false;
    }   // 소수 확인용 for 문 종료
    // for문 중에 나누어 떨어지는 수가 나오지 않았으므로 a는 소수이다 true
    return true;
}

int main(){
	cout << isPrimeNumber(97) << "\n";  // 결과값 1  즉, true이다
						//  0이면 false
	return 0;
}

 

 

---

 

에라토스테네스의 체

---

n까지의 모든 소수를 구하고자 할때 사용한다

1은 소수가 아니므로 2부터 시작하여 n까지 i가 증가하며 다음의 순서를 따른다

1. 배열에 i값을 초기화하여 넣는다

2. i는 자기 자신을 제외한 i의 배수를 배열에서 모두 지운다 (자기 자신은 남긴다. 추후 소수로 모을 예정)

3. 다음 i가 이미 지워져 있으면 계산은 건너 뛰고 다음 i로 넘어뛴다

4. i가 확인하려는 범위인 n까지 소수판별은 마쳤으면 남아있는 숫자들이 소수이다. 출력한다

// 10만까지의 범위에서 소수를 구해보자
int number = 100000;

// 범위의 숫자마다 true false를 담을 배열을 만든다. 넉넉히 범위 10만 +1 개의 배열을 만든다
// 1보다 조금 더 커도 된다. 배열 선언시의 관행 같은 것이다
int a[100001];

// sieve 체
void primeNumberSieve() {

	// 확인할 범위를 0외의 숫자로 초기화해준다. 0만 아니면 다른 숫자로 초기화해도 된다
	for(int i = 2; i <= number; i++){
    	a[i] = i;	
    }
    
    // 2부터 시작해서 number까지 i를 하나씩 움직이며 실행한다  
 	for(int i = 2; i <= number; i++){
    
    	// 이미 a[i] 값이 0으로 지워졌다면 그 i는 계산하지 않고 건너뛴다 다음 i를 실행한다    	
        if(a[i] == 0) continue;
        
        // 이미 지워진 숫자가 아니라면 (자신은 안건드리고) i의 배수부터 범위내의 모든
        // i의 배수(j+=i)를 지워준다(a[j]=0 그 수의 배수인 배열에 0을 할당한다)
        for(int j = i+i; j<=number; j+=i){
        	a[j] = 0;
        }
    }  // 지우는 과정의 for문 종료
    
    // 소수가 아닌 것은 0으로 모두 지워졌으니 다시 돌면서 남은 소수들을 출력해준다
    // 원하는 목적에 따라 출력이 아닌 벡터로 모아 만들어도 된다
    for(int i = 2; i<= number; i++){
    // 출력마다 한 칸씩 띄고 모두 출력 후 줄바꿈 후 끝내기 위한 코드
    	if(a[i] != 0)
        	cout << a[i] << " ";
    }
	cout << "\n";
}