[백준] 1978번 : 소수찾기 with python3, java

11 Oct 2018

Reading time ~1 minute

문제링크 : https://www.acmicpc.net/problem/1978

어떤 수 N이 소수인지 아닌지 판별하는데 걸린 시간 복잡도 : O(루트 N)

input()
a = list(map(int ,input().split()))
count=0

def is_prime(x):
    if x < 2 :
        return False
    i = 2
    while i*i <= x:
        if x % i == 0:
            return False
        i += 1

    return True

for i in a:
    if is_prime(i):
        count += 1

print(count)

import java.util.*;
public class Main {
    public static boolean is_prime(int x) {
        if (x <= 1) {
            return false;
        } else if (x == 2) {
            return true;
        }
        for (int i=2; i*i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        while (n-- > 0) {
            if (is_prime(sc.nextInt())) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}