Baekjoon Algorithm | Problem 1978: Finding Primes

Source

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

Problem

Solve Baekjoon Online Judge problem 1978, Finding Primes.

Input

Follow the input format and constraints given in the original problem statement.

Output

Print the answer required by the problem.

Sample Input 1

4 1 3 5 7

Sample Output 1

Algorithm Classification

Math
Number Theory
Primality Testing
Sieve of Eratosthenes

Solution

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);
        }
    }
}