백준 소수 찾기(1978) java

문제

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

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

4
1 3 5 7

예제 출력 1

3

try1

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String args[]) throws IOException {

         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         int T = Integer.parseInt(br.readLine());
         StringTokenizer st = new StringTokenizer(br.readLine(), " ");
         int totalNum = 0;
         int N = 0;

         for(int i = 0; i < T; i++){
            N = Integer.parseInt(st.nextToken());
            int K = 0;

            if(N != 1){
                for(int j = 1; j <= N; j++){
                    if(N % j == 0){
                        K++;
                    }
                }
                if(K <= 2){
                    totalNum++;
                }
            }
         }
         System.out.println(totalNum);
    }
}

🔖 Notes

• 또 다른 소수를 구할 때의 방법(참고 : https://st-lab.tistory.com/80 )

  while(st.hasMoreTokens()) {
          
  			// 소수인경우 true, 아닌경우 false   
  			boolean isPrime = true;
  			
  			int num = Integer.parseInt(st.nextToken());
  			
  			if(num == 1) {
  				continue;
  			}
  			for(int i = 2; i <= Math.sqrt(num); i++) {
  				if(num % i == 0) {
  					isPrime = false;
  					break;
  				}
  			}
  			if(isPrime) {
  				count++;
  			}
  }

• Math.sqrt(num) : 제곱근 구하기
• 아래 방법을 사용했으면 시간복잡도가 좀 더 좋았을텐데.. 너무 단순하게만 생각해봤네. 다음번에는 한 번 더 생각해보는 걸로!
• 합성수 Number = A * B 에서 A와 B 중 적어도 하나는 Number의 제곱근보다 작거나 같다.
  • Number의 제곱근 이상의 수로 나누면 이전의 검사한 수 중 약수인 수를 약수로 갖는다. or 약수가 아니다.
  • 그래서 소수를 판별할 때는 Number-1 까지가 아닌 Number의 제곱근까지만 검사하면 된다(!)
• 에라토스테네스의 체 : 여러 개의 소수를 구하고 싶을 때 체를 거르듯이 하는 방법을 쓰면 매우 쉽게 판별할 수 있다. O(N^1/2)의 시간복잡도를 갖는다.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity

public class Eratos {
	public static void main(String[] args) {
		// ArrayList로 구현
		ArrayList<Boolean> primeList;

		// 사용자로부터의 콘솔 입력
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		// n <= 1 일 때 종료
		if(n <= 1) return;

		// n+1만큼 할당
		primeList = new ArrayList<Boolean>(n+1);
		// 0번째와 1번째를 소수 아님으로 처리
		primeList.add(false);
		primeList.add(false);
		// 2~ n까지 소수로 설정
		for(int i=2; i<=n; i++ )
			primeList.add(i, true);

		// 2부터  ~ i*i <= n
		// 각각의 배수들을 지워간다.
		for(int i=2; (i*i)<=n; i++){
			if(primeList.get(i)){
				for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
				//i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
			}
		}
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		for(int i=0; i<=n; i++){
			if(primeList.get(i) == true){
				sb.append(i);
				sb.append(",");
			}
		}
		sb.setCharAt(sb.length()-1, '}');

		System.out.println(sb.toString());

	}
}