kingsubin

// 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! 자료구조와 함께 배우는 알고리즘 입문