Show problems as
Classic problem #204MediumArrayMathEnumerationNumber TheoryPrimality TestSieve TheoryPrime Number Sieve

Count Primes

Real-world version: Indivisible Catalogue Numbers
Tracked in this browser only
Read Count Primes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstCounting Occurrences · Binary Search, animated step by step

A parts depot gives every stock item a whole-number catalogue code. The stocktaking team calls a code indivisible when the code is 2 or larger and no whole number other than 1 and the code itself divides it exactly.

A clerk is auditing the codes below a cut-off limit. Report how many indivisible codes are smaller than limit. Codes equal to limit are outside the audit window and must not be counted, and when limit is so small that the window holds nothing, the tally is 0.

Examples

Example 1

Input
limit = 25
Output
9

The indivisible codes under the cut-off are 2, 3, 5, 7, 11, 13, 17, 19 and 23, so the clerk records nine of them.

Example 2

Input
limit = 3
Output
1

Only the code 2 sits under the cut-off. The code 3 equals the cut-off, so it stays out of the window.

Example 3

Input
limit = 97
Output
24

Twenty-four codes below 97 have no divisor other than 1 and themselves; 97 itself is indivisible but is excluded by the cut-off.

Constraints

  • 0 <= limit <= 5 * 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_indivisible_codes(limit: int) -> int:
Java
public int countIndivisibleCodes(int limit)

More on the same topics