BOJ 1978 소수 찾기

1 개요[ | ]

BOJ 1978 소수 찾기

소수 판별법을 연습해 봅니다
알고리즘 분류: 수학, 에라토스테네스의 체

2 C++[ | ]

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if(n < 2) return false;
    for(int i=2; i<=n/2; i++) {
        if(n%i==0) return false;
    }
    return true;
}

int main() {
    int N, X;
    cin >> N;
    int count = 0;
    for(int i=0; i<N; i++) {
        cin >> X;
        if(isPrime(X)) count++;
    }
    cout << count << '\n';
}

3 Java[ | ]

import java.util.Scanner;
public class Main {
	static boolean isPrime(int n) {
        if( n<2 ) return false;
        for( int i=2; i<=(int)Math.sqrt(n); i++)
            if( n%i == 0) return false;
        return true;
    }
	public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int prime_count = 0;
        int n;
        for(int i=0; i<size; i++) {
            n = sc.nextInt();
            if( isPrime(n) ) prime_count++;
        }
        System.out.println( prime_count );
    }
}

import java.util.Scanner;
public class Main {
	static boolean is_prime(int n) {
		if( n < 2 ) return false;
		if( n < 4 ) return true;
		if( n%2==0 || n%3==0 ) return false;
		for(int i=5; i*i<=n; i+=6 ) if(n%i==0 || n%(i+2)==0) return false;
		return true;
	}
	public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int prime_count = 0;
        int n;
        for(int i=0; i<size; i++) {
            n = sc.nextInt();
            if( is_prime(n) ) prime_count++;
        }
        System.out.println( prime_count );
    }
}

4 PHP[ | ]

<?php
function is_prime($n) {
    if( $n<2 ) return false;
    for($i=2; $i<=sqrt($n); $i++) if($n%$i == 0) return false;
    return true;
}
$n = intval(fgets(STDIN));
$arr = explode(' ', rtrim(fgets(STDIN)));
$cnt = 0;
foreach($arr as $ele) {
    if(is_prime($ele)) $cnt++;
}
echo $cnt;

5 Python[ | ]

def is_prime(x):
    import math
    if x<2: return False
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0: return False
    return True
N = int(input())
a = [int(i) for i in input().split()]
cnt = 0
for i in a:
    if is_prime(i): cnt += 1
print(cnt)

6 같이 보기[ | ]