λ¬Έμ
λ¬Έμ λ§ν¬ https://www.acmicpc.net/problem/1978
- 첫 μ€μ μμ κ°μ Nμ΄ μ£Όμ΄μ§λ€. Nμ 100μ΄νμ΄λ€. λ€μμΌλ‘ Nκ°μ μκ° μ£Όμ΄μ§λλ° μλ 1,000 μ΄νμ μμ°μμ΄λ€.
- μ£Όμ΄μ§ μ Nκ° μ€μμ μμκ° λͺ κ°μΈμ§ μ°Ύμμ μΆλ ₯νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μμ΄λμ΄
- μμ μ°ΎκΈ°λ₯Ό 보μλ§μ μλΌν μ€ν
λ€μ€μ μ²΄κ° μκ°μ΄ λ¬λ€. (μ¬μ€ ν¬κΈ°κ° μμμ νλνλ μ°Ύμλ μκ°μ΄κ³Ό μλ¬μ κ² κ°μ§λ§ κ·Έλλ μ’ λ ν¨μ¨μ μΈ λ°©λ²μΌλ‘ νμ΄λ³΄κ³ μ μλΌν μ€ν
λ€μ€μ μ²΄λ‘ νκΈ°λ‘ κ²°μ¬νλ€. γ
γ
)
κ²ͺμ μνμ°©μ€
- μ²μμ λ¬Έμ 보μλ§μ μλΌν μ€ν λ€μ€μ 체λ₯Ό μ΄μ©νμ¬ νμλΌκ³ μκ°νμ§λ§ λ§μ μ¬μ©νλ €κ³ λ³΄λ μλ¦¬κ° κΈ°μ΅μ΄ μλμ μ‘°κΈ κ³ μνλ€... μμΌλ‘ μκ³ λ¦¬μ¦μ μ΄λ¦λ§ κΈ°μ΅νμ§λ§κ³ λ°©λ²κΉμ§ μ λλ‘ μμ§νλλ‘ κ³΅λΆν΄μΌκ² λ€..!
μ½λ
import java.io.*;
import java.util.*;
// μλΌν μ€ν
λ€μ€μ 체λ₯Ό μ¬μ©
// μμλ€μ λλμΌλ‘ λΉ λ₯΄κ³ μ ννκ² κ΅¬νλ μκ³ λ¦¬μ¦
public class BOJ1978 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// λ²μκ° 1000μ΄λ―λ‘
boolean prime[] = new boolean[1001];
// boolean ν¨μκ° μ²μμ falseλ‘ μ΄κΈ°ν λλ―λ‘ trueκ° μμκ° μλ κ±Έλ‘ νμ
// 0κ³Ό 1μ μμκ° μλλ―λ‘ λ°λλ‘ λ°κΏμ€
prime[0] = true;
prime[1] = true;
for(int i = 2; i <= Math.sqrt(1000); i++){
// iκ° μμμΌ κ²½μ°,
if(!prime[i]){
// iμ λ°°μλ μμκ° μλλ―λ‘ boolean κ°μ λ°λλ‘ λ°κΏμ€
for(int j = i * i; j <= 1000; j = j + i){
prime[j] = true;
}
}
}
int N = Integer.parseInt(br.readLine());
int cnt = 0;
// μμμΈμ§ νλ³ν μ μ
λ ₯λ°κΈ°
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){
int a = Integer.parseInt(st.nextToken());
// falseμΌ κ²½μ°, μμμ΄λ―λ‘ cnt + 1
if(!prime[a]){
cnt = cnt + 1;
}
}
System.out.println(cnt);
}
}
'μκ³ λ¦¬μ¦' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Java] BOJ 2292 λ²μ§ (0) | 2024.07.10 |
---|---|
[Java] BOJ 2231 λΆν΄ν© (0) | 2024.07.10 |
[Java] BOJ 30802 μ°μ»΄ν€νΈ (0) | 2024.07.09 |
[Java] BOJ 4153 μ§κ°μΌκ°ν (0) | 2024.07.09 |
[Java] BOJ 1620 λλμΌ ν¬μΌλͺ¬ λ§μ€ν° μ΄λ€μ (2) | 2024.07.08 |