티스토리 뷰
반응형
백준 1124번 언더프라임
https://www.acmicpc.net/problem/1124
1124번: 언더프라임
자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면,
www.acmicpc.net
![](https://blog.kakaocdn.net/dn/X53Db/btsowcwZcaZ/Ffko6oe3UKt2yjjSL9CvCK/img.jpg)
![](https://blog.kakaocdn.net/dn/dI8J2K/btsowcjuU1u/lLpsx6VyXf3pqcTEOjKuUk/img.jpg)
정답 코드
#include<iostream>
#include<math.h>
using namespace std;
int arr[100001] = { 1,1 };
void prime() {
for (int x = 2; x <= sqrt(100001); x++) {
for (int y = x * x; y <= 100001; y += x) {
if (arr[y] != 0)
continue;
else
arr[y] = 1;
}
}
}
int abc(int a) {
int count = 0;
for (int x = 2; x <= a; x++) {
if (arr[x]==0&&a % x == 0) {
a /= x;
count++;
x--;
}
if (a == 1)
break;
}
return count;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a, b;
cin >> a >> b;
prime();
int sum = 0;
for (int x = a; x <= b; x++) {
int d = abc(x);
if (arr[d] == 0)
sum++;
}
cout << sum;
}
문제 풀이
언더프라임에 관한 문제입니다. 언더프라임이란, 어떤 수 N을 소인수분해하여 얻은 소수의 갯수가 소수인 것을 말합니다. 여기서는 에라토스테네스의 체를 이용해서 먼저 소수를 구하여야 합니다. 일반적인 방식으로 구할 시에는 시간복잡도가 더 커지기 때문에 시간초과가 뜹니다. 그 후 입력받은 수를 소수로 나눠주고 그 갯수가 소수인지 판정만 하면 쉽게 풀 수 있습니다.
반응형
'Algorithm > BOJ' 카테고리의 다른 글
백준 1157번 C++ (0) | 2023.07.21 |
---|---|
백준 1152번 C++ (0) | 2023.07.21 |
백준 1120번 C++ (2) | 2023.07.21 |
백준 1110번 C++ (0) | 2023.07.21 |
백준 1094번 C++ (0) | 2023.07.21 |
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 자바
- 이분 매칭
- js
- C++ Stack
- 카운팅 정렬
- CSS
- java
- 우선순위 큐
- html
- 유니온 파인드
- DFS
- 알고리즘 공부
- 자바스크립트
- 백준 풀이
- 알고리즘
- 최단 경로
- C++
- 백준
- 투 포인터
- HTML5
- 유클리드 호제법
- 자료구조
- BFS
- DP
- Do it!
- 스택
- 에라토스테네스의 체
- c++ string
- 세그먼트 트리
- 반복문
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
글 보관함