Funcia
Lv.1mathsieve

Count Primes up to N

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Return how many primes are in 1..n.

Examples

nresult
104
10
10025

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(n: int) → int

Constraints

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

Expected complexity

Time
O(N log log N)
Space
O(N)

Examples

nExpected
104
10
10025

Hint

Hint

Use the sieve of Eratosthenes: for every surviving p with p2≤np^2 \le n, cross out p2,p2+p,…p^2, p^2 + p, \dots. Use a byte array. Trial division up to k\sqrt{k} for every number is O(NN)O(N\sqrt{N}) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness409verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.