3주차. 소수찾기

1978. 소수찾기
https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

📌문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

  
- 예제1

  📝입력

4
1 3 5 7

  💻출력

3

  

    
📌풀이
1. 에라토스테네스의 체 (14164 KB,124ms)
 

package week3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 소수찾기 {
    static int max = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 배열 넣기
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(arr[i], max);
        }
        System.out.println(solution(arr));
    }

    static public int solution(int[] arr){
        int answer = 0;
        boolean[] primeCheck = new boolean[max+1];
        // 예외처리
        if(max < 2) return answer;
        primeCheck[1] = true;

        for(int i = 2; i <= Math.sqrt(max); i++){
            if(primeCheck[i] == false){
                for(int j = i*i; j <= max; j= j+i){
                    primeCheck[j] = true;
                }
            }
        }

        for(int n : arr){
            if(primeCheck[n] == false) answer++;
        }
        return answer;
    }

}

   - 전주에 했었던 에라토스테네스의 체 방식을 활용함

   - 입력받은 값의 최대 값을 기준으로 소수를 체크한다.

  
2. 간단한 소수 체크 (14036 KB,124ms)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = 0;
        for(int i = 0; i < n; i++){
            int num = Integer.parseInt(st.nextToken());
            if(isPrime(num)) answer ++;
        }
        System.out.println(answer);
    }

    static boolean isPrime(int num) {
        if(num == 1) return false;
        for(int i=2; i<num; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }

}

- 입력받은 숫자를 나눠서 나머지가 0이라면 소수가 아니므로 false 리턴

 

.

.

.

시간이 똑같네..?

에라토스테네스의 체를 활용하면 시간 초가 더 줄거라는 생각때문에(전 주에 했던거라 사실 복붙하기도 편해서) 첫번째 방법으로 문제를 풀고 스터디를 했는데 대부분의 스터디 팀원분들이 2번 방식으로 풀었더라.

내 생각이 잘못됐을 수도 있을 것 같아 다시 짜보고 제출해보니 오잉? 비슷하게 시간이 걸리는 거 같음

 

2번이 더 낫겠다 싶었음