[에라토스테네스의 체] Java로 구현하기
에라토스테네스의 체 - 소수를 쉽게 구하는 체(거름망) 그림으로 알아보자. 우선 숫자를 100까지 써본다. 그 후 각 숫자에 따라서 그 수의 배수인 수들은 모두 제거해나가기 시작한다. 2를 고르고, 2의 배수를 모두 지우고, 3을 고르고 3의 배수를 모두 지우고, 4는 2의 배수로 지워져있기 때문에 4의 배수는 다시 지우지 않아도 된다. 이렇게 지워지고 남은 수들은 모두 소수이다. 왜냐면 자기 자신과 1을 곱해야 나오는 수이기 때문이다. 100이 소수인지 확인하기 위해서 일일이 100보다 작은 모든 수들로 확인할 필요는 없다. 이 방식대로 하면 시간복잡도가 O(n^2)이 되어버리고 소수인지 판별하려는 숫자가 너무 커지게 되면 코드 실행 시간이 매우 커지게 될것이다. 하지만, 소수인지 확인하려는 수의 제곱..
Algorithm/수학 코딩
2019. 12. 8. 23:14
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 윈도우 복붙
- 연산 순서
- printf 계산 순서
- c언어 필드 폭지정
- 배열 메모리
- 배열 메모리 할당
- res 의미
- CLion 한글
- 배열 주의사항
- CLion 한글 깨짐
- 복붙하기
- C언어 printf문
- printf문 연산자
- 모바일 앱 설계
- MinGW 한글 깨짐
- C언어 배열 선언
- 앱 프로그래밍
- 계산 순서
- 다이나믹 프로그래밍
- C언어 한글
- C언어 한글 깨짐
- c언어 공백 출력
- 필드 폭 지정
- 증감연산자 계산 순서
- 안스 프로젝트 구조
- printf 스택
- python list 팁
- 백준
- MinGW 한글
- manifest 의미
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함