Funcia
Lv.1mathsieve

N 이하의 소수 개수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 n이 주어집니다. 1부터 n까지의 수 중 소수가 몇 개인지 반환하세요.

소수는 1과 자기 자신만으로 나누어떨어지는 1보다 큰 정수입니다.

입출력 예

nresult
104
10
10025

입출력 예 설명

예 1 — 2, 3, 5, 7 네 개입니다.

예 2 — 1은 소수가 아닙니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(n: int) → int

제한 사항

  • 1≤1 \le n ≤107\le 10^7

기대 복잡도

시간
O(N log log N)
공간
O(N)

입출력 예

n기대 출력
104
10
10025

힌트

힌트

수마다 나눠 보는 대신, 소수의 배수를 지워 나가는 에라토스테네스의 체를 쓰세요.

  1. is_prime[0..n]을 모두 참으로 두고 0과 1만 거짓으로 바꿉니다.
  2. p = 2부터 p2≤np^2 \le n인 동안, p가 아직 소수로 남아 있으면 p2,p2+p,p2+2p,…p^2, p^2 + p, p^2 + 2p, \dots를 모두 지웁니다. p2p^2보다 작은 배수는 더 작은 소수가 이미 지웠습니다.
  3. 남은 참의 개수가 답입니다.

n이 10710^7이라 배열은 bool/바이트 배열로 잡으세요. int 배열은 메모리를 4배 씁니다.

복잡도 목표

수마다 k\sqrt{k}까지 나눠 보는 풀이는 O(NN)O(N\sqrt{N})이라 효율성 테스트에서 시간 초과가 납니다. 체는 O(Nlog⁡log⁡N)O(N \log \log N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness409판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.