numericpattern135.py

def get_primes(count):
    """Get the first 'count' prime numbers using Sieve of Eratosthenes."""
    if count == 0:
        return []

    if count < 6:
        limit = 15
    else:
        import math
        limit = int(count * (math.log(count) + math.log(math.log(count)) + 2))

    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False

    for i in range(2, int(limit ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * i, limit + 1, i):
                sieve[j] = False

    primes = [i for i in range(2, limit + 1) if sieve[i]]

    while len(primes) < count:
        limit *= 2
        sieve = [True] * (limit + 1)
        sieve[0] = sieve[1] = False
        for i in range(2, int(limit ** 0.5) + 1):
            if sieve[i]:
                for j in range(i * i, limit + 1, i):
                    sieve[j] = False
        primes = [i for i in range(2, limit + 1) if sieve[i]]

    return primes[:count]


def generate_prime_grid(n):
    """
    Generate a grid filled with prime numbers in specific row order.

    Args:
        n: The size of the grid (n x n)
    """
    primes = get_primes(n * n)

    grid = [[0] * n for _ in range(n)]
    idx = 0

    for row in range(n):
        for col in range(n):
            grid[row][col] = primes[idx]
            idx += 1

    max_width = len(str(primes[-1]))
    for row in grid:
        print(' '.join(str(num).rjust(max_width) for num in row))


n = int(input())
generate_prime_grid(n)