백준 1978번 자바 : 소수 찾기

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        if(n > 100) return;

        int prime = 0;
        for (int i=0; i<n; i++) {
            int num = in.nextInt();
            if(isPrime(num)) {
                prime++;
            }
        }
        System.out.println(prime);
    }

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

에라토스테네스의 체

한편, 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 n보다 작은 어떤 수 m이 m=abm=ab라면 aa와 bb 중 적어도 하나는 루트n
이하이다. 즉 n보다 작은 합성수 m은 루트n
보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, 루트n
이하의 수의 배수만 지우면 된다.

boolean is_Prime(int Number) {

	if(Number == 1){
		return false;	
	}
 
  
	for(int i = 2; i <= Math.sqrt(Number); i++) {
  
		if(N % i == 0) return false;
      
	}
  
	return true;
}