Skip to content

Latest commit

 

History

History
27 lines (19 loc) · 1.15 KB

README.md

File metadata and controls

27 lines (19 loc) · 1.15 KB
Raw

Prime Numbers

I tested three different algorithms to find prime number between 1 - n.

  1. Trial Division
  2. Sieve of Eratosthenes
  3. Dijkstra's Approach

Results

Note: Tested in Bun v1.1.13 runtime.

1 Million

1million

10 Million

10million

Conclusion

The results are surprising because Dijkstra's Approach is expected to be faster than Trial Division but slower than Sieve of Eratosthenes. My theory is that since JavaScript does not have a native heap implementation, this makes Dijkstra's Approach slower.

Please feel free to open Issues or PRs if you find any problems or you can improve the implementation.

References

  1. Trial Division (Wikipedia page)
  2. Sieve of Eratosthenes (Wikipedia page)
  3. Dijkstra's Prime Algorithm (Webpage)
  4. Dijkstra's Hidden Prime Finding Algorithm (YouTube Video)