소수 구하는 방법, 에라토스테네스의 체

문자열 속에 소수 찾기 문제가 있었는데, 소수를 어떻게 찾을 수 있을지 고민해봤다.

소수는 1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수이다.

기본적인 소수성 테스트_ 소수를 구하는 방법 1

소수인지 아닌지를 isPrime 함수를 만들어서 boolean을 통해 true or false로 값을 받아낸다.

    public static boolean isPrime(int n) {
        if (n <= 1) {  
            return false;
        }

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

• 음수, 0, 1은 소수가 나올 수 없으니, 조건문을 이용해 제외하고
• 제곱근으로 나누어서 나머지가 0이되면 합성수이므로 제외
• 나머지 숫자값들은 소수이므로 true를 리턴해준다.

에라토스테네스의 체_ 소수를 구하는 방법 2

i=2 부터 √n 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시킨다.

public static boolean[] sieveOfEratosthenes(int n) {

	
    boolean[] primes = new boolean[n + 1]; 
    
    Arrays.fill(primes, true);  

    primes[0] = primes[1] = false;  

    for (int i = 2; i * i <= n; i++) {  
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i) {  
                primes[j] = false;
            }
        }
    }

    return primes; 
}

• 0부터 n까지의 숫자를 나타내는 n+1 크기의 배열을 초기화
• 처음에 배열 모든 요소를 true로 설정해, 소수라고 가정
• 0과 1은 소수가 아닌 것을 명시적 표시
• 첫 번째 for문 : 2부터 n의 제곱근까지 반복
• 두 번째 for문 : i에 대해 i*i로 시작하는 배수들은 소수가 아닌 것으로 표시
• i가 소수면 true

😊👍알고리즘은 하면 할 수록, 누적이 쌓일 수록 내공도 쌓이는 느낌이다.

문제내용과 풀이과정은 아래 링크에 적어놓았다.
https://velog.io/@deppll6239/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%85%8C%EC%8A%A4%ED%8A%B8-java

TIL에 들어갈 내용
1. (원인파악)오늘 문제를 접했는지
2. (원인분석)어떤 시도를 해보았는지
3. (해결)어떻게 해결을 했는지
4. (회고)무엇을 새롭게 깨달았는지