Tất cả thử thách
Trung bình 2 đã giải Tỷ lệ chấp nhận 66.7%

List Primes With a Sieve

Find primes up to a limit by marking composite multiples.

Bạn sẽ học được gì

  • Đánh dấu hợp số trong mảng Boolean
  • Bắt đầu gạch từ p × p
  • Thu thập các số nguyên tố còn lại

Đề bài

Return all prime numbers from 2 through limit. A prime is an integer greater than 1 divisible only by 1 and itself. Use the sieve idea: keep the next unmarked number and mark its larger multiples as composite. List results in ascending order.

Implement sieve_primes(limit).

Input

limit: The largest number that may be included.

Output

Return the primes in ascending order, or an empty list if none exist.

Ràng buộc

0 ≤ limit ≤ 100,000. The upper bound is inclusive. Output tests verify results, not the exact algorithm used.

Ví dụ

Ví dụ 1
Đầu vào:
limit = 12

Kết quả mong đợi:
expected = [2, 3, 5, 7, 11]
Đầu vào:
long long limit = 12;

Kết quả mong đợi:
std::vector<long long> expected = {2, 3, 5, 7, 11};
Đầu vào:
long limit = 12;

Kết quả mong đợi:
long[] expected = new long[] {2, 3, 5, 7, 11};

Giải thích

Mark multiples of 2 and 3 as composite. The remaining values up to 12 are 2, 3, 5, 7, and 11.

Ví dụ 2
Đầu vào:
limit = 1

Kết quả mong đợi:
expected = []
Đầu vào:
long long limit = 1;

Kết quả mong đợi:
std::vector<long long> expected = {};
Đầu vào:
long limit = 1;

Kết quả mong đợi:
long[] expected = new long[] {};

Giải thích

Prime numbers begin at 2, beyond this limit.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Đánh dấu hợp số bắt đầu từ mỗi ứng viên nguyên tố chưa bị đánh dấu và tiếp tục đến giới hạn.

Gợi ý 2

Chỉ những số còn nguyên chưa bị đánh dấu ở cuối mới là số nguyên tố.

Gợi ý 3

Dừng đánh dấu bội số khi bình phương của ứng viên vượt quá giới hạn.

Độ phức tạp mong đợi

thời gian O(n log log n), bộ nhớ phụ O(n)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 1,002 ms - 5/5 Xem code
2 KKKaneki Ken Python 1,006 ms - 3/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 2 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.