백준 1978번 : 소수 찾기 [Java, C++]

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

1978번: 소수 찾기

에라토스테네스의 체 문제를 풀려다 소수 구하는 방법 상기시키는 겸 자바 연습 겸 새로 풀어보았다.

 

간단풀이

입력 받은 수 개수에서 소수가 아닌 수의 개수를 빼주었다. 

1. 1은 소수가 아니다. if 수가 1일때 카운트 제외

2. 2는 소수이다. 별다른 조치 X

3. 3이상의 수 부터는 검사 시작

    해당 수를 2부터 자기자신-1 까지 나누어줌 

    만약 나누어 떨어지는 수가 있다면 소수 X -> 카운트 제외

            나누어 떨어지는 수가 없다면 소수 O -> 그냥 그대로

Java 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		int N;
		Scanner sc = new Scanner(System.in); //스캐너 객체 생성
		
		
		N = sc.nextInt(); //정수 입력받기
		int[] num = new int[N]; //입력받은 수 배열에 넣기
		int cnt = N; //소수의 개수
		
		for(int j = 0;j<N;j++) {
			num[j] = sc.nextInt();
			if(num[j] == 1) { //1은 소수가 아니다
				cnt --;
			}else if(num[j] > 2) { //2는 소수이므로 아무 동작 x, 3부터 판별
				for(int i = 2; i < num[j]; i++) {
					
					if(num[j] % i == 0) { //소수가 아님
						cnt --;
						break;
					}
				}
			}
		}
		System.out.println(cnt);
	}
}

 

C++ 코드

#include <iostream>
using namespace std;

int main() {
	int N;
	cin >> N;
	int* list = new int[N];

	for (int i = 0; i < N; i++) {
		cin >> list[i];
	}
	
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (list[i] == 1) { cnt ++; }
		else {
			for (int j = 2; j < list[i]; j++) {
				if (list[i] % j == 0) {
					cnt++;
                    break;
				}
			}
		}
	}
	cout << (N-cnt);

	delete[] list;
	return 0;
}