Re: The joy of FORTRAN

antispam@fricas.org (Waldek Hebisch) wrote or quoted:

critique of decomposed PrimeGenerator.  Personally I find
the Knuth-based pre-decomposed version the clearest one:
- it is obviously correct once one gets loop invariants
- it is compact enough that loop invariants can be easily guessed.

  I talked about this with my old buddy, the chatbot,
  and here's our attempt (in Python):

# Prime Number Generator
# ======================
# This program generates the first `n` prime numbers using an iterative approach.
#
# Algorithm Overview:
# -------------------
# The algorithm generates prime numbers by iteratively testing candidate numbers
# for primality. It maintains two key data structures:
#
# 1. A list of discovered primes (`primes`): This list stores all prime numbers
#    found so far.
#
# 2. A list of multiples of these primes (`multiples`): This list tracks multiples
#    of previously discovered primes to help determine whether a candidate number
#    is composite (not prime).
#
# The algorithm works as follows:
# - Start with the first prime number, 2.
# - Test each subsequent odd number (skipping even numbers, which are not prime).
# - For each candidate number:
#   - If it equals the square of the largest discovered prime, mark it as composite.
#   - Otherwise, check if it is divisible by any previously discovered primes.
# - If no divisors are found, the candidate is prime and is added to the list of primes.
#
# This approach avoids unnecessary checks (e.g., skipping even numbers) and dynamically
# updates multiples as new primes are discovered. While not as efficient as sieve-based
# algorithms for generating large ranges of primes, it is well-suited for generating a
# specific number of primes (`n`).

def generate_primes(n):
    """
    Generate the first `n` prime numbers using an iterative approach.

    Args:
        n (int): The number of prime numbers to generate.

    Returns:
        list: A list containing the first `n` prime numbers.

    Algorithm Details:
    ------------------
    - The function starts with the first prime number (2) and iteratively tests
      odd numbers for primality.
    - It uses a helper function `is_prime` to test each candidate number against
      previously discovered primes and their multiples.
    - The process continues until `n` primes have been found.
    """
    # Step 1: Handle edge cases where `n` is less than or equal to 0.
    if n <= 0:
        return []  # No primes to generate for invalid input.

    # Step 2: Initialize the list of primes with the first prime number (2).
    primes = [2]

    # Step 3: Initialize a list to track multiples of discovered primes.
    #         This helps in marking non-prime (composite) numbers efficiently.
    multiples = [2]

    # Step 4: Begin testing candidate numbers starting from 3 (the next odd number).
    candidate = 3

    # Step 5: Continue testing candidates until we have found `n` primes.
    while len(primes) < n:
        # Check if the current candidate is prime using a helper function.
        if is_prime(candidate, primes, multiples):
            # If it is prime, add it to the list of primes.
            primes.append(candidate)

        # Increment the candidate by 2 to skip even numbers (which are not prime).
        candidate += 2

    # Step 6: Return the list of generated prime numbers.
    return primes


def is_prime(candidate, primes, multiples):
    """
    Determine if a candidate number is prime by checking divisibility against
    previously discovered primes and their multiples.

    Args:
        candidate (int): The number being tested for primality.
        primes (list): The list of discovered prime numbers.
        multiples (list): The list of multiples of discovered primes.

    Returns:
        bool: True if the candidate is prime, False otherwise.

    Algorithm Details:
    ------------------
    - If the candidate equals the square of the largest discovered prime,
      it is marked as composite and added to the list of multiples.
    - Otherwise, check divisibility using previously tracked multiples. If any
      multiple matches the candidate, it is composite (not prime).
    - If no divisors are found, the candidate is considered prime.
    """
    # Retrieve the largest discovered prime and calculate its square.
    largest_prime = primes[-1]
    square_of_largest = largest_prime * largest_prime

    # If the candidate equals the square of the largest prime,
    # add it to multiples and mark it as composite.
    if candidate == square_of_largest:
        multiples.append(candidate)
        return False

    # Check divisibility using previously tracked multiples.
    for i in range(1, len(multiples)):
        # Update multiples until they exceed or match the candidate.
        while multiples[i] < candidate:
            multiples[i] += 2 * primes[i]

        # If any multiple matches the candidate, it is not prime.
        if multiples[i] == candidate:
            return False

    # If no divisors are found, return True (the candidate is prime).
    return True


# Example Usage
# =============
if __name__ == "__main__":
    # Let's generate and print the first 10 prime numbers:
   
    num_primes = 10
   
    print(f"The first {num_primes} prime numbers are:")
   
    # Call `generate_primes` to compute them and print them in a readable format.
   
    print(generate_primes(num_primes))