Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize LinearSieve with segmented sieves #115

Open
byeongkeunahn opened this issue Oct 1, 2024 · 0 comments
Open

Optimize LinearSieve with segmented sieves #115

byeongkeunahn opened this issue Oct 1, 2024 · 0 comments

Comments

@byeongkeunahn
Copy link
Collaborator

Currently, LinearSieve uses a linear sieving algorithm but it is not very performant. It achieves ~600 ms up to 10**7 on Baekjoon Online Judge.

A cache-aware sieve algorithm called segmented sieves can dramatically improve the sieving performance. It is described here: https://github.com/kimwalisch/primesieve/wiki/Segmented-sieve-of-Eratosthenes

The above project is licensed under BSD-2. Hence, if the implementation is to be directly translated and adapted, it is possible, and we would need to add corresponding license acknowledgements.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant