[에라토스테네스의 체] 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
- res 의미
- 앱 프로그래밍
- CLion 한글 깨짐
- printf 스택
- c언어 공백 출력
- 다이나믹 프로그래밍
- 배열 메모리
- 안스 프로젝트 구조
- 배열 메모리 할당
- 증감연산자 계산 순서
- 백준
- 필드 폭 지정
- 복붙하기
- printf문 연산자
- manifest 의미
- MinGW 한글
- CLion 한글
- 모바일 앱 설계
- C언어 한글 깨짐
- 연산 순서
- python list 팁
- C언어 printf문
- printf 계산 순서
- 배열 주의사항
- C언어 배열 선언
- MinGW 한글 깨짐
- 계산 순서
- c언어 필드 폭지정
- 윈도우 복붙
- C언어 한글
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함