이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 95 번째 글 입니다.
- Part 1 - 백준(1003번): 피보나치 함수
- Part 2 - 백준(1010번): 다리놓기
- Part 3 - 백준(1012번): 유기농 배추
- Part 4 - 백준(10159번): 저울
- Part 5 - 백준(10164번): 격자상의 경로
- Part 6 - 백준(1018번): 체스판 다시 칠하기
- Part 7 - 백준(1018번): 체스판 다시 칠하기
- Part 8 - 백준(1022번): 소용돌이 예쁘게 출력하기
- Part 9 - 백준(10775번): 공항
- Part 10 - 백준(10816번): 숫자 카드2
- Part 11 - 백준(10816번): 숫자카드 2
- Part 12 - 백준(10819번): 차이를 최대로
- Part 13 - 백준(10830번): 행렬 곱셈
- Part 14 - 백준(10844번): 쉬운 계단수
- Part 15 - 백준(10868번): 최소값
- Part 16 - 백준(1092번): 배
- Part 17 - 백준(11003번): 최솟값 찾기
- Part 18 - 백준(1102번): 발전소
- Part 19 - 백준(11048번): 이동하기
- Part 20 - 백준(11053번): 가장 긴 증가하는 부분 수열
- Part 21 - 백준(11054번): 가장 긴 바이토닉 부분 수열
- Part 22 - 백준(11055번): 가장 긴 증가하는 부분 수열2
- Part 23 - 백준(11057번): 오르막 수
- Part 24 - 백준(1120번): 문자열
- Part 25 - 백준(11403번): 경로 찾기
- Part 26 - 백준(11404번): 플루이드
- Part 27 - 백준(1149번): RGB 거리
- Part 28 - 백준(11559번): puyo puyo
- Part 29 - 백준(11655번): ROT13
- Part 30 - 백준(1167번): 트리의 지름
- Part 31 - 백준(11722번): 가장 감소하는 부분 수열
- Part 32 - 백준(12015번): 가장 긴 증가하는 부분 수열(LIS) 2
- Part 33 - 백준(12851번): 숨바꼭질2
- Part 34 - 백준(12852번): 1로 만들기 2
- Part 35 - 백준(12865번): 평범한 배낭
- Part 36 - 백준(1300번): K번째 수
- Part 37 - 백준(1325번): 효율적인 해킹
- Part 38 - 백준(13549번): 숨바꼭질3
- Part 39 - 백준(13913번): 숨바꼭질4
- Part 40 - 백준(14002번): 가장 긴 증가하는 부분 수열 4
- Part 41 - 백준(1431번): 시리얼 넘버
- Part 42 - 백준(1436번): 영화감독 숌
- Part 43 - 백준(14499번): 주사위 굴리기
- Part 44 - 백준(14888번): 연산자 끼워넣기
- Part 45 - 백준(14889번): 스타트와 링크
- Part 46 - 백준(14891번): 톱니바퀴
- Part 47 - 백준(15658번): 연산자 끼워넣기 2
- Part 48 - 백준(15686번): 치킨 배달
- Part 49 - 백준(1697번): 숨바꼭질
- Part 50 - 백준(1697번): 숨바꼭질
- Part 51 - 백준(1707번): 이분 그래프(Bipartite Graph)
- Part 52 - 백준(1708번): 볼록 껍질
- Part 53 - 백준(17136번): 색종이 붙이기
- Part 54 - 백준(1717번): 집합의 표현
- Part 55 - 백준(17298번): 오큰수
- Part 56 - 백준(17626번): Four Squares
- Part 57 - 백준(18870번): 좌표 압축
- Part 58 - 백준(1890번): 점프
- Part 59 - 백준(1918번): 후위 표기식
- Part 60 - 백준(1929번): 소수 구하기
- Part 61 - 백준(1963번): 소수 경로
- Part 62 - 백준(1965번): 상자넣기
- Part 63 - 백준(1976번): 여행가자
- Part 64 - 백준(1987번): 알파벳
- Part 65 - 백준(1992번): 쿼드트리
- Part 66 - 백준(2003번): 수들의 합2
- Part 67 - 백준(20040번): 사이클 게임
- Part 68 - 백준(2042번): 구간 합 구하기
- Part 69 - 백준(2108번): 통계학
- Part 70 - 백준(2110번): 공유기 설치
- Part 71 - 백준(2156번): 포도주 시식
- Part 72 - 백준(2193번): 이친수
- Part 73 - 백준(2231번): 분해합
- Part 74 - 백준(2250번): 트리의 높이와 너비
- Part 75 - 백준(2293번): 동전 1
- Part 76 - 백준(2294번): 동전 2
- Part 77 - 백준(2343번): 기타 레슨
- Part 78 - 백준(2468번): 안전 영역
- Part 79 - 백준(2512번): 예산
- Part 80 - 백준(2529번): 부등호
- Part 81 - 백준(2565번): 전깃줄
- Part 82 - 백준(2581번): 소수
- Part 83 - 백준(2583번): 영역구하기
- Part 84 - 백준(2630번): 색종이 만들기
- Part 85 - 백준(2644번): 촌수계산
- Part 86 - 백준(2667번): 단지번호붙이기
- Part 87 - 백준(2751번): 수 정렬하기 2
- Part 88 - 백준(2798번): 블랙잭
- Part 89 - 백준(2904번): 수학은 너무 쉬워
- Part 90 - 백준(2986번): 파스칼
- Part 91 - 백준(3015번): 오아시스 재결합
- Part 92 - 백준(3190번): 뱀
- Part 93 - 백준(3190번): 벽 부수고 이동하기
- Part 94 - 백준(4195번): 친구 네트워크
- Part 95 - This Post
- Part 96 - 백준(4963번): 섬의 개수
- Part 97 - 백준(4991번): 로봇 청소기
- Part 98 - 백준(5373번): 큐빙
- Part 99 - 백준(5437번): 불
- Part 100 - 백준(6171번): 땅따먹기
- Part 101 - 백준(6603번): 로또
- Part 102 - 백준(6603번): 로또
- Part 103 - 백준(7562번): 나이트의 이동
- Part 104 - 백준(7568번): 덩치
- Part 105 - 백준(7576번): 토마토
- Part 106 - 백준(7579번): 앱
- Part 107 - 백준(7785번): 회사에 있는 사람
- Part 108 - 백준(9012번): 괄호
- Part 109 - 백준(9020번): 골드바흐의 추측
- Part 110 - 백준(9184번): 신나는 함수 실행
- Part 111 - 백준(9251번): LCS
- Part 112 - 백준(9421번): 소수상근수
- Part 113 - 프로그래머스: 가장 큰 정사각형 찾기
▼ 목록 보기
실버2 : 수학 문제이다.
생각
소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.
Code
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAX 123456*2
using namespace std;
int N;
bool isPrime[MAX+1];
void SeiveofEratosThenes(){
fill(isPrime+2, isPrime+MAX+1, true);
for (int i = 2; i*i <= MAX; i++) {
if (isPrime[i] == false) continue;
for (int j = i*i; j <= MAX; j+=i) {
isPrime[j] = false;
}
}
}
int main(){
SeiveofEratosThenes();
while (1) {
int count = 0;
cin >> N;
if (N == 0) {
break;
}
for (int i = N+1; i <= 2*N; i++) {
if (isPrime[i]) count++;
}
cout << count << '\n';
}
return 0;
}