Median Prime Number(s) Calculator
demo.mov
Clone the app. ensure you have Docker properly configured, with compose v2
to run the application simple run the following script in the root directory:
docker compose up
You can test the front end and back end individually run the snippet of script at the root directory of the codebase npm install would need to be run to ensure dev dependencies are available. Frontend:
cd client
npm install
npm run test
Backend:
cd server
npm install
npm run test
overview of the stack and structure.
built with CRA create react app: typescript and tailwind css.
├── components
│ ├── **/*.tsx # Common UI components for the application
│
├── Hooks
│ ├── **/*.ts # Custom hooks for handling requirements of the application
│
├── App.tsx # Parent Component
│
└── index.tsx # Entry point to application
built with Express
├── primeHelpers.ts # helper utility functions
│
└── server.ts # Entry point for server
Prime-finding algorithms were researched to identify a suitable candidate to implement. Sieve of Eratosthenes was considered and tested locally and identified to be a source of a bottleneck as it utilized large amounts of memory and took a long amount of time to compute for any number greater than 1M. Sieve of Atkin was ultimately considered the most suitable option for this implementation with less time complexity and less utilization of memory.
Comparision
Theoretical Time Complexity:
- Sieve of Eratosthenes: O(n log log n)
- Sieve of Atkin: O(n/log log n)
Local Testing (avg of 3):
| Limit | Sieve of Atkin | Sieve of Eratosthenes |
|---|---|---|
| 40000000 | 7.189s | 8.852s |
| 50000000 | 8.163s | 44.682s |
| 60000000 | 12.456s | heap out of memory |
| 70000000 | 14.367s | heap out of memory |
| 80000000 | 15.159ss | heap out of memory |
- 4+ years of Production Node Experience
- 6+ years of Production React Experience
- Ahmed Al Amawi