소수찾기(2)

배지원·2022년 11월 3일

알고리즘

목록 보기

11/16

프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/12921

1. 문제

소수 찾기

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하기

소수란?

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

1은 소수가 아니다.

2. 문제분석

n의 값을 입력받는다.
1~n 사이의 소수를 구하기 위해 여러가지 식을 대입하여 숫자를 나눈다.
소수인지 아닌지 판별한다.

🚫 제한조건 1. n은 2이상 1000000이하의 자연수입니다.

3. 설계

(1) 에라토스테네스의 체를 이용한다.

임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법
소수가 아닌 값을 제외시켜 최종적으로 소수인 값만 남기는 방식
이전에 했던 코드가 O(N)이라면 에라토스테네스의 체는 O(Log N)정도의 속도로 가장 빠르다

① 2를 제외한 2의 배수를 제거

② 3를 제외한 3의 배수를 제거

③ 4는 이미 제거 되었으므로 생략

④ 위의 과정을 원하는 수만큼 반복

(2) 리스트로 구현

50까지의 소수를 찾고싶을때
① 2~50까지 리스트에 삽입

<// 1은 소수가 아니므로 2부터 시작
for(int i =2; i<=num; i++){
   nums.add(i);
}

② 2부터 50까지 돌면서 그 수를 제외한 배수를 제거

// 2부터 num-1번값까지
// 일반 for문으로 i<=num으로 돌리면 num값이 클경우 너무 많은 반복을 하게됨
// 따라서 i의 제곱이 num보다 작거나 같을때까지 반복하게 되면 모든 소수를 찾을 수 있고 반복횟수도 적어짐
for(int i=2; i*i<=num; i++) {
   for (int j = 1; j < nums.size(); j++) {
       // 배수이면서 자기자신은 아니여야 함
       if (nums.get(j) % i == 0 && nums.get(j) != i) {
          nums.remove(j);
       }
   }
}

③ 최종적으로 남은 리스트 사이즈를 반환

4. CODE

public class PrimeNumber {

    public int solution(int num){
        List<Integer> nums = new ArrayList<>();

        // 1은 소수가 아니므로 2부터 시작
        for(int i =2; i<=num; i++){
            nums.add(i);
        }

        // removeif( )  list의 메서드로 조건문을 통해 해당하는 값은 제거시킨다.

        // 2부터 num-1번값까지
        // 일반 for문으로 i<=num으로 돌리면 num값이 클경우 너무 많은 반복을 하게됨
        // 따라서 i의 제곱이 num보다 작거나 같을때까지 반복하게 되면 모든 소수를 찾을 수 있고 반복횟수도 적어짐
        for(int i=2; i*i<=num; i++) {
            for (int j = 1; j < nums.size(); j++) {
                // 배수이면서 자기자신은 아니여야 함
                if (nums.get(j) % i == 0 && nums.get(j) != i) {
                    nums.remove(j);
                }
            }
        }
        
        return nums.size();
    }

    public static void main(String[] args) {
        PrimeNumber p = new PrimeNumber();
        System.out.println(p.solution(10));
        System.out.println(p.solution(5));
    }
}