Liệt kê số nguyên tố

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

Bob15324

Dạng bài

Điểm: 800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho số nguyên dương \(n\), hãy liệt kê các số nguyên tố trong phạm vi từ \(1\) tới \(n\).

Input

Vào từ thiết bị nhập chuẩn số nguyên dương \(n \leq 10^6\).

Output

Ghi ra thiết bị xuất chuẩn các số nguyên tố tìm được theo thứ tự tăng dần, mỗi số một dòng.

Example

Test 1

Input

Output

Bình luận

solution python

Python

def a(l):
    p = [False] * (l + 1)
    s = int(l**0.5) + 1  
    for x in range(1, s):
        for y in range(1, s):
            n = 4 * x**2 + y**2
            if n <= l and (n % 12 == 1 or n % 12 == 5):
                p[n] = not p[n]
            n = 3 * x**2 + y**2
            if n <= l and n % 12 == 7:
                p[n] = not p[n]
            n = 3 * x**2 - y**2
            if x > y and n <= l and n % 12 == 11:
                p[n] = not p[n]
    for n in range(5, s):
        if p[n]:
            for k in range(n**2, l + 1, n**2):
                p[k] = False

    r = [2, 3] + [n for n in range(5, l + 1) if p[n]]
    return r
b = int(input())
nt = a(b)
for i in nt:
    print(i)

1 bình luận nữa