[BOJ] 1978. 소수 찾기 (C,Python3)

• 코딩 초보. 구현을 목표로 하였기에 비효율적일 수 있습니다.

---

1978. 소수 찾기 

 

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

 

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

 

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

 

---

1.C99

 

#include <stdio.h>

main() {
	int n,s, num[1001] = { 0, }, prime[1001] = { 0,0, },count=0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}

	//prime 저장 
	for (int i = 2; i < 1001; i++) {
		prime[i] = 1; 
	}
	
	for (int i = 2; i <= 31; i++) {
		if (prime[i] == 1) {
			for (int j = 2; i * j < 1000; j++) {
				prime[i * j] = 0; 
			}
		}
	}

	//prime count 
	for (int i = 0; i < n; i++) {
		for (int j = 0;j<1000; j++) {
			if (prime[j] == 1 && num[i] == j) count++; 
		}
	}

	printf("%d", count); 

}

C언어를 배웠을 때 했었던 실습과 유사한 방식으로 코드를 구현하였다. 먼저 입력받는 수의 범위가 1000까지이므로 소수를 저장한 배열도 1000까지 해주었다. 소수가 아닌 인덱스에는 0을, 소수인 인덱스에는 1을 저장하도록 하였다. 1000의 제곱근인 31까지 for반복문을 수행하도록 하였다. 

 

num에 입력한 수를 차례차례 for 이중 반복문을 이용하여 prime 배열에 1이 저장되어 있고 (소수이고), 그 인덱스 값과 num에 저장된 수가 같을 경우 count를 증가시키도록 하여 소수를 카운트하도록 하였다. 

 

---

2.Python

 

count=0
n=int(input())
num=list(map(int,input().split()))
prime=[]

#prime list
for i in range(2,1001):
    prime.append(i)
for i in prime:
    for j in range(2,1001):
        s=i*j
        if s>1001:
            break
        if s in prime:
            prime.remove(s)
#count prime
for i in range(n):
    for j in range(len(prime)):
        if num[i]==prime[j]:
            count+=1
        
print(count)

비슷한 방식으로 구현했다. 

여기에서는 prime 리스트를 소수가 아닌 수를 prime 리스트에서 차례대로 remove하는 방식으로 만들었다.