小数を求めるアルゴリズム

小数を求めるアルゴリズム

bool solution1(int x) 
{
	if (x < 2) {	// 0, 1은 소수가 아님
    	return false;
    }
    
	for (int i = 2; i < x; ++i) {	
   		if (x % i == 0) {
        	return false;
        }
    }
    
    return true;
}

bool solution2(int x) 
{
	if (x < 2) {	// 0, 1은 소수가 아님
    	return false;
    }
    
	for (int i = 2; i < x / 2; ++i) {	
   		if (x % i == 0) {
        	return false;
        }
    }
    
    return true;
}

bool solution3(int x) 
{
	if (x < 2) {
    	return false;
    }
    
    for (int i = 2; i <= sqrt(x); ++i) {
    	if (x % i == 0) {
        	return false;
        }
    }
    
    return true;
}

bool primeArray[MAX];	// MAX 구하고자 하는 수의 최댓값

void initPrime(int n) 
{
    fill(bool, bool + n, true);	// 처음엔 모두 소수로 본다.
    
    for (int i = 2; i * i <= n; ++i) {
    	if (primeArray[i]) {
        	for (int j = i * i;j <= n; j += 1) {
            	primeArray[j] = false;
            }
        }
    }
    
}

bool solution4(int x) 
{
    if (x < 2) {
    	return false;
    } 
    
    initPrime(1000000);
    
    return primeArray[x];
}