수학) 소수 판별법: 에라토스테네스의 체

1. 주어진 범위에 속한 소수를 모두 구할 때: 에라토스테네스의 체

for(int i = 2 ; i <= arrSize ; i++){
		if(arr[i] == -1){ //이미 소수가 아닌 수로 계산된 수는 
			continue; //더 계산하지 않는다
		}else{
			for(int j = i + i ; j <= arrSize ; j = j + i){ //현재 수의 배수는 소수가 아니므로, 
				if(arr[j] != -1){ //이미 지워진 수가 아니면
					arr[j] = -1; //지워준다
				}
			}
		}
	}

 

2. 하나의 숫자(n)가 소수인지 판별할 때: n을 2부터 n제곱근까지 나눠본다

#include <iostream>
#include <cmath> //sqrt

using namespace std;

int n,sqrtn;
bool isitprime = true;

sqrtn = (int)sqrt( n);  

	for (int j = 2; j < sqrtn + 1; j++) { //소수 판별을 위한 피연산 값: 2부터 n의 제곱근까지
		if (n % j == 0) {
			isitPrime = false; // 소수가 아님
			break; //더 계산할 필요 없이 소수가 아님
		}
	}

	}