Algorithm/문제

17. 소수(에라토스테네스의 체)

2023. 6. 12. 15:27

소수 구하는 방법론에서는 에라토스테네스 체가 가장 빠르다. 이중 포문으로 돌려서 20만이 넘으면 time리미트가 뜬다. 

ch = new int [21] //배열은 0부터 시작이니까 

0,1은 소수의 대상이 아니므로 for문의 i가 2일 때부터로 한다. 

ch[i] == 0 이면 소수이므로 (2의 배수가 2, 4, 6, ...이라면 2는 2, 4, 6의 약수라는 의미인데 ch[i]가 체크가 안되고 0값 그대로 있다는 거는 2부터 i전까지의 숫자 중 i를 배수로 갖는 숫자가 없다는 걸 의미한다. 즉 i의 약수가 존재하지 않았다.)

카운팅하고 i의 배수들을 체크해야한다. (0 -> 1)

 

import java.util.Scanner;

public class Main {
    public int solution(int n) {
        int answer = 0;
        int[] ch = new int[n + 1]; //n+1로 해야 n번 index까지 생김
        for (int i = 2; i <= n; i++) {
            if(ch[i] == 0){
                answer ++;
                for (int j = i; j <= n; j=j+i) //i의 배수 찾기
                    ch[j]=1;
            }
        }
        return answer;
    }
   public static void main(String[] args){
       Main T = new Main();
       Scanner kb = new Scanner(System.in);
       int n=kb.nextInt();
       System.out.println(T.solution(n));

   }
}

i의 배수 찾는 과정에서 j = j+1 주의!

 

다른풀이

-boolean을 이용하여 true-> 소수가 아님

 import java.util.Scanner;

public class Main {
    public int solution(int n) {
        int answer = 0;
        boolean[] s = new boolean[n + 1];
        s[0] = true;
        s[1] = true;
        for (int i = 2; i <= n; i++) {
            if (s[i] == false) answer ++;
            for (int j = i*i; j <=n ; j+=i)
                s[j]=true;
        }
        return answer;
    }
   public static void main(String[] args){
       Main T = new Main();
       Scanner kb = new Scanner(System.in);
       int n=kb.nextInt();
       System.out.println(T.solution(n));

   }
}

 

'Algorithm > 문제' 카테고리의 다른 글

19. 점수계산  (0) 2023.06.14
18. 뒤집은 소수 ★  (0) 2023.06.12
16. 피보나치 수열  (0) 2023.06.01
15. 가위 바위 보  (1) 2023.05.30
14. 보이는 학생  (0) 2023.05.29
'Algorithm/문제' 카테고리의 다른 글
  • 19. 점수계산
  • 18. 뒤집은 소수 ★
  • 16. 피보나치 수열
  • 15. 가위 바위 보
챛채
챛채
챛채
챛 Development Log
챛채
전체
오늘
어제
  • IT (105)
    • Front (5)
      • Thymeleaf (1)
    • Language (4)
      • JAVA (4)
    • Spring (38)
      • JPA (4)
      • Spring boot (13)
      • Security (1)
      • MSA (6)
      • Kafka (3)
    • DBMS (6)
      • Redis (6)
    • CS (1)
    • Algorithm (45)
      • 이론 (3)
      • 백준 (1)
      • 문제 (41)
    • 자격증 (1)
      • 정보처리기사 (필기) (0)
      • 정보처리기사 (실기) (1)
    • 프로젝트 (3)
      • chaelog (3)

블로그 메뉴

    최근 글

    hELLO · Designed By 정상우.
    챛채
    17. 소수(에라토스테네스의 체)
    상단으로

    티스토리툴바

    개인정보

    • 티스토리 홈
    • 포럼
    • 로그인

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.