create python code to count prime numbers till million
- User
create python code to count prime numbers till million
Assistant
Certainly! Below is a Python code to count the number of prime numbers up to one million using the Sieve of Eratosthenes algorithm, which is efficient for this purpose.
def count_primes(n): if n < 2: return 0 # Initialize a list to track prime numbers is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False # 0 and 1 are not prime numbers # Implement the Sieve of Eratosthenes for i in range(2, int(n**0.5) + 1): if is_prime[i]: for j in range(i*i, n + 1, i): is_prime[j] = False # Count the number of prime numbers prime_count = sum(is_prime) return prime_count # Count primes up to 1,000,000 n = 1_000_000 prime_count = count_primes(n) print(f"The number of prime numbers up to {n} is {prime_count}")Explanation:
-
Initialization:
- We create a list
is_primewhereis_prime[i]will beTrueifiis a prime number andFalseotherwise. - We set
is_prime[0]andis_prime[1]toFalsebecause 0 and 1 are not prime numbers.
- We create a list
-
Sieve of Eratosthenes:
- We iterate over each number
ifrom 2 to the square root ofn. - For each
i, ifis_prime[i]isTrue, we mark all multiples ofi(starting fromi*i) asFalsebecause they cannot be prime.
- We iterate over each number
-
Counting Primes:
- We sum the
is_primelist to get the count of prime numbers.
- We sum the
-
Output:
- Finally, we print the count of prime numbers up to one million.
When you run this code, it will efficiently count and print the number of prime numbers up to one million.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.