Задача · алгоритмы лёгкая Python ·

Count primes

Return how many prime numbers are strictly less than n (0 ≤ n ≤ 5,000,000).

Сигнатура

def count_primes(n: int) -> int:

Примеры

count_primes(10)  # -> 4
count_primes(0)  # -> 0
count_primes(2)  # -> 0

Плюс 6 скрытых тестов и 1 тест на большом входе с лимитом времени; их входные данные не показываются. Условия задач моделям дают на английском.

1-е местоAnthropic Claude Haiku 5.5решено · 10 из 10 тестовответ за 1.1 с · работа 96 мс · $0.0001

✓	count_primes(10)ожидалось 4	<1 мс
✓	count_primes(0)ожидалось 0	<1 мс
✓	count_primes(2)ожидалось 0	<1 мс

✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс⏱ 90 мс

Код

def count_primes(n: int) -> int:
    if n <= 2:
        return 0
    size = n
    sieve = bytearray([1]) * size
    sieve[0] = 0
    sieve[1] = 0
    i = 2
    while i * i < size:
        if sieve[i]:
            start = i * i
            count = (size - 1 - start) // i + 1
            sieve[start::i] = bytes(count)
        i += 1
    return sum(sieve)

2-е местоSpaceXAI Grok Build 0.1решено · 10 из 10 тестовответ за 6.9 с · работа 622 мс · $0.0021
✓ count_primes(10)ожидалось 4 <1 мс
✓ count_primes(0)ожидалось 0 <1 мс
✓ count_primes(2)ожидалось 0 <1 мс
✓ <1 мс✓ <1 мс✓ <1 мс✓ <1 мс✓ 1 мс✓ 1 мс⏱ 615 мс
Код
```
def count_primes(n: int) -> int:
    if n <= 2:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n, i):
                is_prime[j] = False
    return sum(is_prime)
```

2-е местоDeepSeek V4 Pro 0423решено · 10 из 10 тестовответ за 2.1 с · работа 628 мс · $0.0004

✓	count_primes(10)ожидалось 4	<1 мс
✓	count_primes(0)ожидалось 0	<1 мс
✓	count_primes(2)ожидалось 0	1 мс

✓ <1 мс✓ <1 мс✓ 2 мс✓ <1 мс✓ 2 мс✓ 2 мс⏱ 618 мс

Код

def count_primes(n: int) -> int:
    if n <= 2:
        return 0
    
    # Sieve of Eratosthenes
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n, i):
                is_prime[j] = False
    
    return sum(is_prime)

4-е местоMoonshotAI Kimi K2.7 Codeне решено · 0 из 10 тестовответ за 96 с · $0.01

ответ оборвался раньше, чем закончился код

✗	count_primes(10)ожидалось 4в ответе нет кода	—
✗	count_primes(0)ожидалось 0в ответе нет кода	—
✗	count_primes(2)ожидалось 0в ответе нет кода	—

✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода✗ в ответе нет кода⏱ в ответе нет кода

Стоимость токенов: $0.02 · Как проходят и оцениваются раунды →