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

2024. 12. 8. 22:10· 코딩테스트/기초

import java.util.*;
class Main {	
	public int solution(int n){
    	// 소수점의 개수
		int cnt = 0;
        // n과 맞추기 위해선 +1
		int[] ch = new int[n+1];
        // 소수는 2부터 시작이라서 i = 2
		for(int i = 2; i <= n; i++){
        	// ch[i] = 0이면 소수이므로 cnt + 1
			if(ch[i] == 0){
				cnt++;
                현재 소수 i의 배수를 찾기 위한 반복문
				for(int j = i; j <= n; j = j+i){
                	// ch[j] = 1이면 소수가 아니다, j는 i의 배수임으로 소수가 아님
                    ch[j] = 1;
                }
			}
		}
		return cnt;
	}
	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));
	}
}

 

 

 

위키백과 에라토스테네스의 체

 

 

 

import java.util.*;
class Main {    
    public int solution(int n){
        int cnt = 0;
        int[] ch = new int[n+1];
        for(int i = 2; i <= n; i++){
            if(ch[i] == 0){
                cnt++;
                for(int j = i; j <= n; j = j+i){
                    ch[j] = 1;
                }
            }
        }
        return cnt;
    }
    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));
    }
}

'코딩테스트 > 기초' 카테고리의 다른 글

19. 점수계산  (0) 2024.12.10
18. 뒤집은 소수  (1) 2024.12.10
16. 피보나치 수열  (0) 2024.12.08
15. 가위 바위 보  (0) 2024.12.08
14. 보이는 학생  (2) 2024.12.08
'코딩테스트/기초' 카테고리의 다른 글
  • 19. 점수계산
  • 18. 뒤집은 소수
  • 16. 피보나치 수열
  • 15. 가위 바위 보
누리는 귀여워
누리는 귀여워
안녕하세요, 누리 사료값을 벌기 위해 앞으로 나아가는 아버지의 개발 블로그입니다.
누리는 귀여워
누리아버지
누리는 귀여워
전체
오늘
어제
  • 분류 전체보기 (77)
    • Java (0)
      • Spring Boot (16)
      • JPA (1)
    • JavaScript (1)
      • React.js (1)
    • DataBase (3)
      • PostgreSQL (2)
    • DevOps (2)
      • MSA (1)
      • Docker (1)
    • OS (9)
    • Network (0)
    • CS 지식 (0)
    • Error 모음집 (0)
    • 코딩테스트 (32)
      • 기초 (31)
      • 알고리즘 (1)
    • 기타 (7)
    • 쉼터 (3)
      • 잡담 (3)
      • 하루 마무리 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기

공지사항

인기 글

태그

  • git bash
  • postman
  • spring cloud
  • 인텔리제이
  • postgresql
  • Docker
  • kafka sink connect
  • Boot
  • centos
  • Kafka
  • JPA
  • Oracle Cloud
  • GATEWAY
  • kafka connect
  • Dockerfile
  • 깃허브연동
  • spring boot
  • eureka
  • war 배포
  • MSA

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
누리는 귀여워
17. 소수(에라토스테네스 체)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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