https://www.acmicpc.net/problem/1978
풀이
소수는 1과 자기 자신으로만 나누어 떨어지고 그 외의 수로는 나누어 떨어지지 않는 수이다. (단, 1은 소수가 아니다.)
따라서 1과 자기자신의 사이의 수(1과 자기 자신은 제외)들로 모두 나누어보면 소수인지 확인할 수 있다!
1이 소수가 아닌 것에 유의하면서 구현해 보자.
(역으로 생각하여 전체에서 소수가 아닌 것의 개수를 빼면 간편하게 구현할 수 있다. 물론 소수인 것의 개수를 세도 좋습니다.)
C++ 정답코드
더보기
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int res = n;
for(int i = 0; i<n; i++)
{
int x;
cin >> x;
if(x == 1)
{
res--;
continue;
}
for(int j = 2; j<x; j++)
{
if(x%j == 0)
{
res--;
break;
}
}
}
cout << res << endl;
return 0;
}
Python 정답코드
더보기
n = int(input())
arr = map(int,input().split())
res = n
for x in arr:
if(x == 1):
res-=1
continue
for i in range(2,x):
if(x%i == 0):
res-=1
break
print(res)
생각해 보면 좋은 것
위 코드의 연산량은 어떻게 될까?
- N번의 소수 판정을 해야 하고 한 번의 소수 판정에 최대 1000번(주어지는 값의 최댓값)의 루프를 돈다. 최악의 경우 N*1000 = 약 100,000번의 연산이 이루어진다.
ps에서는 보통 컴퓨터가 1초에 1억 번 연산이 가능하다고 잡는데 이를 감안하면 여유롭게 통과하는 연산이다.
이를 Big-O표기법으로 쓰면 O(N * max(A)) (A는 주어진 수들의 리스트)라 할 수 있다.
만약 N의 제한이 크거나 주어진 수의 최댓값이 크다면 어떻게 풀어야 할까?
'알고리즘' 카테고리의 다른 글
백준 1929번 : 소수 구하기 - 에라토스테네스의 체 (C++, Python) (1) | 2024.05.01 |
---|---|
백준 문제 풀이를 위한 기본 c++ 세팅(통합 라이브러리, 빠른 입출력) (1) | 2024.04.27 |
백준으로 알고리즘 공부를 시작해보자! (1) | 2024.04.26 |