def prime1(N):
    primes = []
    d = 2
    l1_count = 0  # (L1)の実行回数カウンタ
    while (d <= N):
        isPrime = True
        t = 2
        while (t < d):
            # (L1) に相当する箇所
            l1_count += 1
            if (d % t == 0):
                isPrime = False
            t = t + 1
        if (isPrime == True):
            primes.append(d)
        d = d + 1
    return primes, l1_count

def prime2(N):
    primes = []
    # 問題文の「isPrime[k]がkの判定を表す」仕様に合わせ、サイズN+1の配列を作成
    is_prime_arr = [True] * (N + 1)
    l2_count = 0  # (L2)の実行回数カウンタ
    
    d = 2
    while (d <= N):
        # [イ] is_prime_arr[d] が true と等しい
        if (is_prime_arr[d] == True):
            primes.append(d)
            t = d * d
            while (t <= N):
                # (L2) に相当する箇所
                l2_count += 1
                is_prime_arr[t] = False
                # [ウ] t + d
                t = t + d
        d = d + 1
    return primes, l2_count

def prime3(N):
    primes = [2]
    # isPrime[k] が 2k+1 の素性判定を表す (k=1のとき3, k=2のとき5...)
    # Nまでの奇数をカバーするサイズを用意
    is_prime_arr = [True] * (N // 2 + 1)
    l3_count = 0  # (L3)の実行回数カウンタ

    d = 3
    while (d <= N):
        # [エ] is_prime_arr[d // 2] が true と等しい
        # ※Pythonでは 2k+1 = d より k = (d-1)/2 です
        k = d // 2
        if (is_prime_arr[k] == True):
            primes.append(d)
            t = d * d
            while (t <= N):
                # (L3) に相当する箇所
                l3_count += 1
                # [オ] t // 2
                is_prime_arr[t // 2] = False
                # [カ] t + 2 * d
                t = t + 2 * d
        d = d + 2
    return primes, l3_count

# --- 動作確認用 ---
N_val = 20
p1, c1 = prime1(N_val)
p2, c2 = prime2(N_val)
p3, c3 = prime3(N_val)

print(f"N={N_val} のとき:")
print(f"prime1: {p1}, (L1)実行回数: {c1}")
print(f"prime2: {p2}, (L2)実行回数: {c2}")
print(f"prime3: {p3}, (L3)実行回数: {c3}")