create python code to count prime numbers till million
- User
create python code to count prime numbers till million
Assistant
Here's an efficient Python implementation using the Sieve of Eratosthenes algorithm to count prime numbers up to one million:
def count_primes(limit): """Count the number of prime numbers up to and including the given limit.""" if limit < 2: return 0 # Create a boolean array "is_prime" and initialize all entries as true is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False # 0 and 1 are not prime # Sieve of Eratosthenes p = 2 while p * p <= limit: # If is_prime[p] is not changed, then it is a prime if is_prime[p]: # Mark all multiples of p as not prime for i in range(p * p, limit + 1, p): is_prime[i] = False p += 1 # Count the primes return sum(is_prime) # Count primes up to 1 million import time start_time = time.time() prime_count = count_primes(1_000_000) end_time = time.time() print(f"Number of primes up to 1,000,000: {prime_count}") print(f"Time taken: {end_time - start_time:.3f} seconds")For even better performance, here's an optimized version that uses memory more efficiently:
def count_primes_optimized(limit): """Optimized version that only checks odd numbers after 2.""" if limit < 2: return 0 if limit == 2: return 1 # Only track odd numbers (even numbers except 2 are not prime) sieve_size = (limit - 1) // 2 is_prime = [True] * sieve_size # Sieve of Eratosthenes for odd numbers only for i in range(3, int(limit**0.5) + 1, 2): if is_prime[(i - 3) // 2]: # Mark odd multiples of i as composite for j in range(i * i, limit + 1, 2 * i): is_prime[(j - 3) // 2] = False # Count primes: 2 plus all odd primes return 1 + sum(is_prime) # Run the optimized version start_time = time.time() prime_count = count_primes_optimized(1_000_000) end_time = time.time() print(f"Number of primes up to 1,000,000: {prime_count}") print(f"Time taken (optimized): {end_time - start_time:.3f} seconds")You can also add functionality to list the primes if needed:
def get_primes(limit): """Return a list of all prime numbers up to the given limit.""" if limit < 2: return [] is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False p = 2 while p * p <= limit: if is_prime[p]: for i in range(p * p, limit + 1, p): is_prime[i] = False p += 1 # Return list of primes return [i for i in range(limit + 1) if is_prime[i]] # Example: Get first 20 primes primes = get_primes(100) print(f"First 20 primes: {primes[:20]}")The Sieve of Eratosthenes is one of the most efficient algorithms for finding all primes up to a given number. The time complexity is O(n log log n) and space complexity is O(n). When you run this code, you'll find there are 78,498 prime numbers less than or equal to 1,000,000.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.