효율적인 소수 구하기 ( 백준 1978 / 1929 )

첫번째 방법 : 단순하게 for문을 다 돌면서 나누어 떨어지는 값이 있는지 확인

value = scanner.nextInt();
int i;
for(i=2 ;i< value; i++)
{
    if( value % i == 0) break; // 소수 아님
}
if(i == value) // 소수!

두번째 방법 : 배열에 미리 소수를 넣어 놓고 검사할 값이 들어오게 되면 그 값보다 작은 소수 까지만 검사!

세번째 방법 : 에라토스테네스 체 알고리즘!

입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다. 그러나 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.

==> 해당 값이 소수인지 아닌지 판별할때는 2<= <= sqrt(n) 까지만 확인 하면 된다!

    public static int isPrime(int value) {
        if(value <= 1) return 0;

        for(int i=2; i * i <= value ; i++)
        {
            if(value % i ==0) return 0;
        }
        return 1;
    }

==> 2~N 까지 소수를 모두 구할때 가장 빠른 알고리즘!

for(int i =2; i<= 1000000; i++)
{
    if(map[i] == 0 ) continue;
    isPrime[index++] = i;
    for(int j= i+i; j<= 1000000; j += i)
    {
        if(map[j] ==0) continue;
        map[j] = 0;
    }
}

public static int N;
    public static int[] arr = new int[1000001];
    public static int start, end;
    public static void isPrime() { // 소수 판별 함수  
        for(int i =2; i * i<= end; i++) {
            if( arr[i] == 0 ) continue;
            for(int j = i+i; j<= end; j+=i) {
                arr[j] =0;
            }
        }
    }
    public static void init() {
        for(int i = 2; i<=end; i++) {
            arr[i] =i;
        }
    }

WonYong-Jang / algorithm

효율적인 소수 구하기 ( 백준 1978 / 1929 ) #6