[백준알고리즘] 1978번: 소수 찾기 -Python, C++

[백준알고리즘] 1978번: 소수 찾기 -Python, C++

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

1978번: 소수 찾기

---

 

다른 분들의 코드를 봤는데 너무 짧고 변수 명도 그냥 알파벳이라 보기 넘 힘들다 ㅠㅠㅠ

 

일단 다른분들은 나처럼 에라토스테네스의 체를 이용한 분들도 계셨고, 1부터 n까지 반복문을 돌면서 안에서 또 3부터? 반복문을 돌리면서 나눠 떨어지는지 확인함으로써 소수인지 판별해서 소수 리스트를 만들어서 사용한 분들도 계셨다.

 

아무튼 나는 에라토스테네스의 체를 사용했다. 에라토스테네스의 체의 위키 링크이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

---

 

안에서도 잘 설명되어있듯이 2의 배수를 지우고, 3의 배수를 지우고, 4는 지워졌으니 넘어가고, 5의 배수를 지우고.... 이러한 방식으로 소수들을 찾아내는 방식이다. 여기서 미리 지워지지 않았던 수들만이 소수가 된다.

import sys

N = int(sys.stdin.readline())
target = list(map(int, sys.stdin.readline().split()))
prime = [1] * 1001
prime[0], prime[1] = 0, 0

# check prime number
for i in range(2, 1001):
    if prime[i]:
        jmp = 2
        while i * jmp <= 1000:
            prime[i*jmp] = 0
            jmp += 1

# count prime number
res = 0
for t in target:
    if prime[t]:
        res += 1

sys.stdout.write(str(res))

 

아래는 C++ 코드이다.

에라토스테네스의 체를 N의 범위인 1000 이하의 자연수에 대해 모두 완성해놓고, 입력이 들어오는 수를 체에 비교하면서 소수 여부를 판단한다.

 

#include <iostream>

bool field[1001];

void eratosthenes(void);
void solve(void);

int main(void)
{
	eratosthenes();
	solve();
	return 0;
}

void eratosthenes(void)
{
	std::fill_n(field, 1001, true);

	field[0] = field[1] = false;
	for (int i = 2; i < 501; i++)
	{
		if (!field[i]) continue;

		int temp = 2;
		while (i * temp <= 1000)
		{
			field[i * temp] = false;
			temp++;
		}
	}
}

void solve(void)
{
	int size;
	std::cin >> size;
	
	int answer = 0;
	for (int i = 0; i < size; i++)
	{
		int temp;
		std::cin >> temp;

		if (field[temp]) answer++;
	}

	std::cout << answer;
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다