[백준] 1978번 - 소수 찾기

문제 >

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력 >

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력 >

주어진 수들 중 소수의 개수를 출력한다.

 

해결방법 > 

n까지의 소수를 찾기위해서 n^(1/2)까지 탐색

 

C++

#include <iostream>
#include <math.h>

using namespace std;

int main(){
    int num, cnt = 0;
    cin >> num;

    for(int i = 0; i < num; i++){
        int temp;
        bool c = true;
        cin >> temp;
        if(temp < 2)
            continue;
        for(int j = 2; j <= sqrt(temp); j++){
            if(temp % j == 0){
                c = false;
                break;
            }
        }
        if(c == true)
            cnt++;
    }

    cout << cnt << '\n';
    return 0;
}

 

JAVA

package baekjoon;

import java.util.*;

public class BOJ_1978 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		int cnt = 0;
		
		for(int i = 0; i < t; i++) {
			int n = sc.nextInt();
			boolean p = true;
			
			if(n == 1)
				continue;
			
			for(int j = 2; j <= Math.sqrt(n); j++) {
				if(n % j == 0) {
					p = false;
					break;
				}
			}
			if(p == true)
				cnt++;
		}
		System.out.println(cnt);
	}
}

 

문제링크 >

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

1978번: 소수 찾기