반응형
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
출력
주어진 수들 중 소수의 개수를 출력한다.
내풀이 )
#include <iostream>
using namespace std;
int main()
{
bool sosu[1005] = { false };
//소수 배열 만들기 => 소수 일땐 true 로 담기게 한다.
// 1-1. 소수 의 법칙을 지정한다.
// 1-2. 소수는 1과 자기 자신 이외에 약수를 가지지 않는 수를 이야기 한다.
for (int sosuNum = 2; sosuNum <= 1000; sosuNum++)
{
bool exist = true;
for (int j = 2; j <= 1000; j++)
{
//소수가 아닐때 false
if (sosuNum != j && sosuNum % j == 0)
{
exist = false;
}
}
if (sosuNum == 2) {
exist = true;
}
sosu[sosuNum] = exist;
}
for (int i = 0; i < 100; i++)
{
if (sosu[i])
{
cout << i << endl;
}
}
//문제
// 입력
// 1. 첫 줄에 개수 n을 입력 받는다.
// 2. n개의 수만큼 숫자를 입력한다.
int n = 0;
cin >> n;
int count = 0;
for (int i = 0; i < n; i++)
{
int num = 0;
cin >> num;
// 처리
// 1. n개의 입력 숫자중에 소수의 개수를 센다.
//소수면 카운트 해준다.
if (sosu[num])
{
count++;
}
}
// 출력
// 1. 셈한 소수의 개수를 출력 한다.
cout << count;
}
문제점 :
소수 배열 만드는 부분과 입력 처리 하는 부분을 동시에 만들수 있는데, 따로 만들어서 사용함으로써 시간 복잡도가 올라갔다.
#include <iostream>
using namespace std;
int main() {
int N, result = 0;
int temp, cnt = 0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> temp;
for (int div = 1; div <= temp; div++) {
if (temp%div == 0)
cnt++;
}
if (cnt == 2) //temp가 소수
result++;
cnt = 0;
}
cout << result << '\n';
}
반응형
'알고리즘' 카테고리의 다른 글
[백준 알고리즘 c++] 문제 16. 소인수분해 11653 (0) | 2022.09.02 |
---|---|
[백준 알고리즘 c++] 문제 15. 소수 찾기2 2581 (0) | 2022.09.02 |
[백준 알고리즘 c++] 문제 13. 두수의 합(배열) 10757 (0) | 2022.08.31 |
[백준 알고리즘 c++] 문제 12. 최소단위로 봉지 나누기 2839 (0) | 2022.08.31 |
[백준 알고리즘 c++] 문제 11. 해당 호수별 인원 파악 2775 (0) | 2022.08.31 |