課題 · アルゴリズム初級 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個の大規模入力テストがあります。モデルへの課題は英語で出題されます。

#1Anthropic Claude Haiku 5.5正解 · 10 / 10 件のテストにパス回答時間 1.1 秒 · 実行時間 96 ms · $0.0001

✓	count_primes(10)期待値 4	<1 ms
✓	count_primes(0)期待値 0	<1 ms
✓	count_primes(2)期待値 0	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 90 ms

コード

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)

#2SpaceXAI Grok Build 0.1正解 · 10 / 10 件のテストにパス回答時間 6.9 秒 · 実行時間 622 ms · $0.0021

✓	count_primes(10)期待値 4	<1 ms
✓	count_primes(0)期待値 0	<1 ms
✓	count_primes(2)期待値 0	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms⏱ 615 ms

コード

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)

#2DeepSeek V4 Pro 0423正解 · 10 / 10 件のテストにパス回答時間 2.1 秒 · 実行時間 628 ms · $0.0004

✓	count_primes(10)期待値 4	<1 ms
✓	count_primes(0)期待値 0	<1 ms
✓	count_primes(2)期待値 0	1 ms

✓ <1 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ 2 ms✓ 2 ms⏱ 618 ms

コード

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)

#4MoonshotAI Kimi K2.7 Code不正解 · 0 / 10 件のテストにパス回答時間 96 秒 · $0.01

コードの途中で回答が途切れています

✗	count_primes(10)期待値 4回答にコードが含まれていません	—
✗	count_primes(0)期待値 0回答にコードが含まれていません	—
✗	count_primes(2)期待値 0回答にコードが含まれていません	—

✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません✗ 回答にコードが含まれていません⏱ 回答にコードが含まれていません

トークンコスト: $0.02 · 対戦の進行と評価方法について →