알고리즘] 1부터 n까지의 소수 갯수 찾기 및 출력

1부터 입력받은 정수 N까지의 자연수 중 소수의 개수 찾기 및 출력하기

 

소수란 약수가 1과 자기 자신만 있는 수를 뜻한다.

 

ex)

6의 약수는 1,2,3,6 -> 소수X

7의 약수는 1,7 -> 소수 O

14의 약수는 1,2,7,14 -> 소수 X

13의 약수 1,13 -> 소수 O

 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("숫자 길이 입력 = ");
        int msg = sc.nextInt();

        int index = 0; //횟수 체크를 위해 카운트함.

        for (int i = 0; i < msg; i++) {
            if (isPrime(i)) { //소수라면 출력
                index++;
                System.out.print(i + " ");
            }
        }
        System.out.println("\n0부터 " + msg + "까지의 소수의 갯수 = " + index);
    }

    public static boolean isPrime(int num) {
        if (num == 1 || num == 0) { // 1과 0은 소수의 체크 항목이 아니기 때문에 바로 리턴.
            return false;
        }
        for (int i = 2; i < num; i++) {
            if (num % i == 0) { // 어떤 수로 나눈 나머지가 0이란 소리는 약수가 존재한다는 소리.
                return false; //입력 받은 정수 - 1 까지 체크한 후 나눠지지 않으면 소수로 판단
            }
        }
        return true;
    }



300x250

 

실행 결과 ->