Baekjoonアルゴリズム | 1978番問題: 素数探し

出典

https://www.acmicpc.net/problem/1978

問題

Baekjoon Online Judgeの1978番問題、素数探しを解きます。

入力

正確な入力形式と制約は元の問題文に従います。

出力

問題で求められる答えを出力します。

サンプル入力 1

4 1 3 5 7

サンプル出力 1

アルゴリズム分類

数学
整数論
素数判定
エラトステネスの篩

解説

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 {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());

            StringTokenizer st = new StringTokenizer(br.readLine());
            int count = 0;
            for (int i = 0; i < n; i++) {
                int a = Integer.parseInt(st.nextToken());
                if (isPrime(a)) {
                    count++;
                }
            }

            System.out.println(count);
        }
    }

    private static boolean isPrime(int num) {
        if (num == 1)
            return false;

        for (int i = 2; i * i <= num; i++) {
            if (num % 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 {

        boolean[] prime = new boolean[1001];
        prime[0] = true;
        prime[1] = true;
        for (int i = 2; i <= Math.sqrt(1000); i++) {
            if (prime[i] == true)
                continue;
            for (int j = i * i; j < 1001; j = j + i)
                prime[j] = true;
        }

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

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

            int count = 0;
            for (int i = 0; i < n; i++) {
                int a = Integer.parseInt(st.nextToken());
                if (prime[a] == false) {
                    count++;
                }
            }

            System.out.println(count);
        }
    }
}