chapter2) 소수 구하기
2020. 7. 9. 20:09ㆍPS/etc
// 1000이하의 소수 구하기
public class Ex11 {
public static void main(String[] args) {
int counter = 0; // 곱셈과 나눗셈의 횟수 (비용)
int ptr = 0; // 찾은 소수의 개수
int[] prime = new int[500]; // 소수를 저장하는 배열
prime[ptr++] = 2;
prime[ptr++] = 3;
for (int n = 5; n <= 1000; n += 2) { // 홀수만
boolean flag = false;
for (int i = 1; prime[i] * prime[i] <= n; i++) {
counter += 2;
if (n % prime[i] == 0) { // 나누어 떨어지면 소수가 아님
flag = true;
break; // 더 이상의 반복은 불필요
}
}
if (!flag) {
prime[ptr++] = n;
counter++;
}
}
for (int i = 0; i < ptr; i++) {
System.out.println(prime[i]);
}
System.out.println("곱셈과 나눗셈을 수행한 횟수 : " + counter);
}
}
- 실습 문제 2-9 ~ 2-11
- 1000이하의 소수 구하기 문제인데 counter로 계산 횟수를 카운팅하고 점점 개선시켰음
- 제곱근 내용이 이해가 잘 안되서 코드 따라쳐봤음
※참조
Do it! 자료구조와 함께 배우는 알고리즘 입문
'PS > etc' 카테고리의 다른 글
chapter2) 그 해의 남은 일 수 구하기 (0) | 2020.07.09 |
---|---|
chapter2) 그 해의 경과 일 수 구하기 (0) | 2020.07.09 |
chapter2) 10진수 변환 (0) | 2020.07.08 |
chapter2) 배열 요소의 합계 구하기 (0) | 2020.07.07 |
chapter2) 배열 역순 정렬 (0) | 2020.07.07 |