Đề 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ụ
Đầ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.
Đầ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.