[C] 소수 판별 1

소수는 약수가 1과 자기 자신만 존재하는 수이다.

또한 약수는 sqrt(N)를 기준으로 대칭입니다.

$36의 약수: 1, 2, 3, 4, (\sqrt{36} \equiv 6), 9, 12, 18, 36$

$50의 약수: 1, 2, 5, (\sqrt{50} \approx 7.07), 10, 25, 50$

즉 2부터 sqrt(N)까지 나누어 보고 나누어 떨어지는 숫자가 없다면 해당 숫자 N은 소수로 판별할 수 있습니다.

기존의 에라스토테네스의 체는 배열이 필요하였다.

하지만, 특정 N에 대한 소수 판별을 할때 배열을 두고 할수는 없으니,

간단하게 쓸수있는 소수 판별을 올려놓는다.

    int isPrime(int n) {
    	int i = 5;
    	if (n%2==0)			//Drop multiple of 2 without 2
    		return n == 2;
    	if (n % 3 == 0)		//Drop multiple of 3 without 3
    		return n == 3;
    	while (i*i <= n) {		//Starting at 5
    		if (n%i == 0)
    			return 0;
    		i += 2;			//Pass even number
    	}
    	return n != 1;
    }