Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-2.5-pro· GoogleHugging Face LMArena Human Preference 140K

Write a python program to find prime number

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Mistralmistral-medium-2505’s answer.
  1. User

    Write a python program to find prime number

  2. Gemini Assistant

    Of course! Here is a complete guide on how to find prime numbers in Python, starting from a basic concept and moving to more efficient methods and a full, user-friendly program.

    What is a Prime Number?

    A prime number is a whole number greater than 1 that has only two divisors: 1 and itself.

    • Examples: 2, 3, 5, 7, 11, 13 are prime numbers.
    • Non-Examples: 4 is not prime (divisible by 1, 2, 4), 6 is not prime (divisible by 1, 2, 3, 6).
    • Special Case: The number 2 is the only even prime number.

    Method 1: The Basic (Brute-Force) Approach

    The simplest way to check if a number n is prime is to try dividing it by every number from 2 up to n-1. If any of these divisions result in a remainder of 0, then the number is not prime.

    This logic is implemented in the function below.

    def is_prime_basic(n):
        """
        Checks if a number is prime using a basic brute-force method.
        """
        # Prime numbers must be greater than 1
        if n < 2:
            return False
    
        # Check for factors from 2 up to n-1
        for i in range(2, n):
            if n % i == 0:
                # Found a factor, so it's not a prime number
                return False
    
        # If the loop completes without finding a factor, it's a prime number
        return True
    
    # --- Example Usage ---
    number = 17
    if is_prime_basic(number):
        print(f"{number} is a prime number.")
    else:
        print(f"{number} is not a prime number.")
    
    number = 18
    if is_prime_basic(number):
        print(f"{number} is a prime number.")
    else:
        print(f"{number} is not a prime number.")
    

    Problem with this approach: It's very slow for large numbers. To check if 999,999,999 is prime, it would have to perform nearly a billion checks!


    Method 2: A More Optimized Approach

    We can make a huge improvement. You only need to check for divisors up to the square root of the number.

    Why? If a number n has a divisor a that is larger than its square root, it must also have a corresponding divisor b that is smaller than its square root (since a * b = n).

    So, if we don't find any divisors up to the square root, we won't find any beyond it either.

    import math
    
    def is_prime_optimized(n):
        """
        Checks if a number is prime using an optimized method.
        """
        # Prime numbers must be greater than 1
        if n < 2:
            return False
        
        # 2 is the only even prime number
        if n == 2:
            return True
        
        # All other even numbers are not prime
        if n % 2 == 0:
            return False
    
        # Check for odd factors from 3 up to the square root of n
        # We can step by 2 because we've already handled even numbers
        # The int(math.sqrt(n)) + 1 is to ensure the range is inclusive
        for i in range(3, int(math.sqrt(n)) + 1, 2):
            if n % i == 0:
                return False
    
        return True
    
    # --- Example Usage ---
    number = 97
    if is_prime_optimized(number):
        print(f"{number} is a prime number.")
    else:
        print(f"{number} is not a prime number.")
    
    number = 99
    if is_prime_optimized(number):
        print(f"{number} is a prime number.")
    else:
        print(f"{number} is not a prime number.")
    

    This version is significantly faster and is the most common method for checking a single number.


    Method 3: Finding All Primes Up to a Limit (Sieve of Eratosthenes)

    If you need to find all prime numbers up to a certain limit N, checking each number individually is inefficient. A much better algorithm is the Sieve of Eratosthenes.

    How it works:

    1. Create a list of booleans from 0 to N, and initially mark all of them as True (potentially prime).
    2. Mark 0 and 1 as False.
    3. Start with the first prime, p = 2.
    4. Mark all multiples of p (4, 6, 8, ...) as False.
    5. Move to the next number that is still marked True (which is 3).
    6. Mark all multiples of 3 (6, 9, 12, ...) as False.
    7. Repeat this process until you've gone past the square root of N.
    8. The numbers that are still marked True are the prime numbers.
    def find_primes_up_to(limit):
        """
        Finds all prime numbers up to a given limit using the Sieve of Eratosthenes.
        Returns a list of prime numbers.
        """
        # Create a boolean list "is_prime" and initialize all entries to True.
        # A value in is_prime[i] will finally be False if i is Not a prime, else True.
        is_prime = [True] * (limit + 1)
        is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime numbers
    
        # Start with the first prime number, 2
        for p in range(2, int(math.sqrt(limit)) + 1):
            # If is_prime[p] is still True, then it is a prime
            if is_prime[p]:
                # Update all multiples of p to False.
                # Start from p*p, because smaller multiples will have been marked by smaller primes.
                for i in range(p * p, limit + 1, p):
                    is_prime[i] = False
    
        # Collect all prime numbers
        primes = []
        for p in range(2, limit + 1):
            if is_prime[p]:
                primes.append(p)
                
        return primes
    
    # --- Example Usage ---
    limit = 100
    prime_numbers = find_primes_up_to(limit)
    print(f"Prime numbers up to {limit}:")
    print(prime_numbers)
    

    Complete, Interactive Program

    This program combines the optimized methods into a user-friendly command-line tool.

    import math
    
    def is_prime(n):
        """
        Checks if a single number n is prime. (Optimized version)
        Returns True if prime, False otherwise.
        """
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        # Check odd divisors from 3 up to the square root of n
        for i in range(3, int(math.sqrt(n)) + 1, 2):
            if n % i == 0:
                return False
        return True
    
    def find_primes_in_range(limit):
        """
        Finds all prime numbers up to a given limit using the Sieve of Eratosthenes.
        Returns a list of prime numbers.
        """
        if limit < 2:
            return []
            
        is_prime_list = [True] * (limit + 1)
        is_prime_list[0] = is_prime_list[1] = False
    
        for p in range(2, int(math.sqrt(limit)) + 1):
            if is_prime_list[p]:
                for i in range(p * p, limit + 1, p):
                    is_prime_list[i] = False
        
        primes = [p for p, is_p in enumerate(is_prime_list) if is_p]
        return primes
    
    def main():
        """Main function to run the interactive program."""
        while True:
            print("\n--- Prime Number Finder ---")
            print("1. Check if a specific number is prime")
            print("2. Find all prime numbers up to a limit")
            print("3. Exit")
    
            choice = input("Enter your choice (1, 2, or 3): ")
    
            if choice == '1':
                try:
                    num_str = input("Enter the number to check: ")
                    number = int(num_str)
                    if is_prime(number):
                        print(f"✅ {number} is a prime number.")
                    else:
                        print(f"❌ {number} is not a prime number.")
                except ValueError:
                    print("Invalid input. Please enter a whole number.")
    
            elif choice == '2':
                try:
                    limit_str = input("Enter the upper limit to find primes: ")
                    limit = int(limit_str)
                    if limit < 2:
                        print("There are no prime numbers below 2.")
                    else:
                        primes = find_primes_in_range(limit)
                        print(f"Found {len(primes)} prime numbers up to {limit}:")
                        print(primes)
                except ValueError:
                    print("Invalid input. Please enter a whole number.")
    
            elif choice == '3':
                print("Exiting the program. Goodbye!")
                break
    
            else:
                print("Invalid choice. Please enter 1, 2, or 3.")
    
    # This ensures the main() function runs only when the script is executed directly
    if __name__ == "__main__":
        main()
    

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.