[Alogrithm] 소수인지 판별하기

숫자 하나가 소수인지 판별하는 알고리즘

public boolean isPrime(int x){

    if (x < 2) 
        return false;
    else 
        for(int i=2 ; i<=(int)Math.sqrt(x) ; i++)
        	if(x%i == 0) 
                return false;
        
    return true;
}

⭐ divisor 의 범위: 2부터 √x 까지만 봐도 충분

---

숫자 범위에서 소수 리스트를 반환하는 알고리즘 - 에라토스테네스의 체

public List primes(int x){
    
    List<Integer> result = new LinkedList<>();
    
    boolean[] isPrimeArr = new boolean[x+1];
    for (int i=0 ; i<isPrimeArr.length ; i++) isPrimeArr[i] = true;
    
    for (int i=2 ; i<=x/2 ; i++){
        for (int j=i+i ; j<=x ; j+=i){
            if(isPrimeArr[j]) isPrimeArr[j] = false;
        }
    }
    
    for (int i=2 ; i<=x ; i++)
        if(isPrimeArr[i]) result.add(i);
    
    return result;
    
}

⭐ 걸러낼 체의 범위: 2부터 x의 ½ 까지만 봐도 충분