1. Subject : 소수를 구하는 방법

1. What I learn?

에라토스테네스의 체!!

소수를 구할 때 사용되는 유용한 방법이다.

소수를 구하는 방법

n이 소수인지 아닌지 구하는 방법은

n이 주어졌을 때 1부터 n까지의 값을 1부터 n으로 나누면 된다.

즉 N^2의 알고리즘이 필요하다.

하지만 에라토스테네스의 체를 이용하면 더 빠른 방법으로 수행할 수 있다.

에라토스 테네스의 체는 소수의 값을 걸러준다. 그러니까 이미 소수라고 판별된 수의 값이 저장되어 있는 것

n이 주어졌을 때 n이 에라토스테네스의 체로 만든 표에 지정된 소수인지 아닌지 판별하면 된다.

9999999까지의 소수를 구하는 방법

    for(int i=2; i<9999999; i++){
        for(int j=i*2; j<9999999; j = j+i){
            era[j] =1;// 
        }
    }
    

여기서 index를 수로 사용하고 소수인지 아닌지를 0,1로 판별한다.

위의 경우에는 1인 경우 소수가 아니고 0인경우 소수가 된다.

2. Review

알고리즘을 풀게되면서 다시 상기한 개념이다. 잊었을 줄 알았는데 다행히 잊지 않았따. 하지만 더더 완벽하게 잊지 않도록 한번 더 기록하도록 하곘다.