[알고리즘] 에라토스테네스의 체

한호성·2022년 5월 13일

알고리즘

에라토스테네스의 체 (소수 구하기)

기본개념

소수 : 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미한다.
즉 소수의 약수는 2개만을 갖고 그 중 하나는 반드시 1이며, 나머지는 자기 자신만을 약수로 갖는다.

개발에서의 소수

개발에서의 소수는 암호에 많이 사용된다. 대표적인 방식이 RSA 암호화 방식이 있다.

"임의 수들의 곱은 구하기 쉽지만 역으로 소인수 분해하는 것은 어렵다."

소수를 소인수 분해하여 PXQ 로 나타내는 것이 어렵다는 말.

RSA-129 =
3490529510847650949147849619903898133417764638493387843990820577 × 32769132993266709549961988190834461413177642967992942539798288533
RSA-129 의 공개키 위의 두수는 소수이다.

현재 인터넷 뱅킹도 RSA -208 을 사용하고 있다고 한다.
RSA-2048 = 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

이것을 PXQ로 나타내는 것이 가능할까?

소수판별 알고리즘 방법

" N 보다 작은 자연수들로 모두 나눠본다. "
" √N 이하의 자연수들로 모두 나눠본다. "
"에라토스테네스의 체"

"에라토스테네스의 체"

소수를 구하는 대표적인 방법 중 하나다.
"K=2 부터 루트N 이하까지 반복하여 자연수들 중 K를 제외한 K의 배수들을 제외시킨다."
-> 아래의 그림과 같은 방식으로

알고리즘 

	public static void make_prime(int N) {
		
        //기본 초기화 값 false Intellj 에서는.. 
        
		prime = new boolean[N + 1];	// 0 ~ N
 
		/*
		소수가 아닌 index = true
		소수인 index = false
		*/
		
		// 2 미만의 N 을 입력받으면 소수는 판별할 필요 없으므로 바로 return
		if(N < 2) {
			return;
		}
        
		prime[0] = prime[1] = true;
		
        
		// 제곱근 함수 : Math.sqrt()
		for(int i = 2; i <= Math.sqrt(N); i++) {
        
			// 이미 체크된 배열이면 다음 반복문으로 skip
			if(prime[i] == true) {
				continue;
			}
        
			// i 의 배수들을 걸러주기 위한 반복문
			for(int j = i * i; j < prime.length; j = j+i) {
				prime[j] = true;
			}
		}
 
	}