Find the first 100 primes via the sieve of eranthroses
- User
Find the first 100 primes via the sieve of eranthroses
Assistant
Here's a JavaScript implementation of the Sieve of Eratosthenes to find the first 100 prime numbers:
function findFirstNPrimes(n) { // We need to determine a large enough upper bound to find n primes // Using a rough estimate based on the prime number theorem const upperBound = Math.ceil(n * (Math.log(n) + Math.log(Math.log(n)))); // Create array of boolean values, initially all true let sieve = new Array(upperBound + 1).fill(true); // 0 and 1 are not prime sieve[0] = sieve[1] = false; // Implement the sieve for (let i = 2; i <= Math.sqrt(upperBound); i++) { if (sieve[i]) { // Mark all multiples of i as non-prime for (let j = i * i; j <= upperBound; j += i) { sieve[j] = false; } } } // Collect the prime numbers let primes = []; for (let i = 2; i <= upperBound && primes.length < n; i++) { if (sieve[i]) { primes.push(i); } } return primes; } // Get the first 100 primes const first100Primes = findFirstNPrimes(100); // Print the results in a formatted way console.log("The first 100 prime numbers are:"); first100Primes.forEach((prime, index) => { // Print 10 numbers per line if (index % 10 === 0) { process.stdout.write('\n' + (index + 1).toString().padStart(3) + '-' + (Math.min(index + 10, 100)).toString().padStart(3) + ': '); } process.stdout.write(prime.toString().padStart(4) + ' '); });This will output the first 100 primes in a nicely formatted way. Here are the first 100 prime numbers:
1-10: 2 3 5 7 11 13 17 19 23 29 11-20: 31 37 41 43 47 53 59 61 67 71 21-30: 73 79 83 89 97 101 103 107 109 113 31-40: 127 131 137 139 149 151 157 163 167 173 41-50: 179 181 191 193 197 199 211 223 227 229 51-60: 233 239 241 251 257 263 269 271 277 281 61-70: 283 293 307 311 313 317 331 337 347 349 71-80: 353 359 367 373 379 383 389 397 401 409 81-90: 419 421 431 433 439 443 449 457 461 463 91-100: 467 479 487 491 499 503 509 521 523 541
Key features of this implementation:
- Uses an optimized upper bound calculation based on the prime number theorem
- Implements the classic Sieve of Eratosthenes algorithm
- Only marks multiples starting from i * i (optimization)
- Formats output in rows of 10 for better readability
- Includes index numbers for easier reference
The Sieve of Eratosthenes is very efficient for finding all primes up to a given limit because:
- It eliminates composite numbers systematically
- Only needs to check up to the square root of the upper bound
- Uses simple array operations
- Doesn't require division operations
This implementation is much more efficient than trial division methods, especially when finding multiple prime numbers. The time complexity is O(n log log n) where n is the upper bound used to find the desired number of primes.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.