소수 찾기 풀이

문제 링크: https://www.acmicpc.net/problem/1978

백준 기본 수학 2 1단계 - 1978번 소수 찾기를 풀어보았다.

 

풀이: 에라토스테네스의 체를 먼저 구현해 소수를 세고, 그 안에 입력값이 있는지를 알아본다.

 

C++

#include <iostream>
#include <cmath>

using namespace std;
int main()
{
  int t;
  scanf("%d",&t);
  int innum[101]; // 입력
  for(int i=0;i<t;i++) cin >> innum[i]; // nums의 n번째 요소가 0이면 n은 소수가 아님
  int nums[1001]; // 소수를 구하기 위한 것
  for(int j=2;j<1001;j++) nums[j]=j;
  nums[0]=0;
  for(int k=2;k<1001;k++)
  {
    if(nums[k]==0) continue;  // 소수가 아니면 넘어감
    for(int l=2*k;l<1001;l+=k) nums[l]=0; // k의 배수는 소수가 아니다
  }
  int count=0;  // 소수 개수
  for(int h=0;h<t;h++) if(nums[innum[h]]!=0) count+=1;
  printf("%d",count);
}

Python

arr=[True]*1000 # 1000까지 소수를 다 찾는다
m=int(1000**0.5)
for i in range(2,m+1):
	if arr[i]==True:
		for j in range(i+i,1000,i):
			arr[j]=False
narr=[i for i in range(2,1000) if arr[i]==True]
n=int(input())
nums=list(map(int,input().split()))
cnt=0
for i in range(n):
	if nums[i] in narr: cnt+=1
print(cnt)

Java