1978 소수 찾기

 

 

 

---

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

public 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[] arr = new int[N];
		int cnt = 0;
		for(int i  = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(prime(arr[i]))
				cnt++;
		}
		System.out.println(cnt);
	}
	static boolean prime(int n) {
		if(n == 1)
			return false;
		for(int i= 2; i < n; i++) {
			if(n%i == 0)
				return false;
		}
		return true;
	}
}

---

 

---

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

public 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[] arr = new int[N];
		int cnt = 0;
		for(int i  = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(prime(arr[i]))
				cnt++;
		}
		System.out.println(cnt);
	}
	static boolean prime(int n) {
		if(n == 1)
			return false;
		for(int i= 2; i < Math.sqrt(n); i++) { //n
			if(n%i == 0)
				return false;
		}
		return true;
	}
}

 

 

---

에라토스테네스의 체

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

public class Main {
	static boolean[] prime_N;
	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];
		int cnt = 0;
		prime_N = new boolean[1001];
		prime(1000);
		for(int i  = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			if(prime_N[arr[i]] != true)
				cnt++;
		}
		System.out.println(cnt);
	}
	static void prime(int n) {
		prime_N[0] = true;
		prime_N[1] = true;
		for(int i = 2; i<=Math.sqrt(1000); i++) {
			if(prime_N[i] == true) {
				continue;
			}
			for(int j = i*i; j<1000+1; j += i) {
				prime_N[j] = true;
			}
		}
	}
}