import openpyxl
from openpyxl import Workbook
import os

def prime_decomposition(n):
    def prime_factors(num):
        factors = []
        divisor = 2
        while divisor * divisor <= num:
            while num % divisor == 0:
                factors.append(divisor)
                num = num // divisor
            divisor += 1 if divisor == 2 else 2
        if num > 1:
            factors.append(num)
        return factors
    
    def compare_sequences(seq1, seq2):
        result = []
        idx1 = 0
        idx2 = 0
        while idx1 < len(seq1) and idx2 < len(seq2):
            if seq1[idx1] == seq2[idx2]:
                idx1 += 1
                idx2 += 1
            else:
                result.append(seq2[idx2])
                idx2 += 1
        while idx2 < len(seq2):
            result.append(seq2[idx2])
            idx2 += 1
        return result
    
    def find_used_primes(sequences):
        primes = set()
        for sequence in sequences.values():
            primes.update(sequence)
        return sorted(list(primes))
    
    # Create level 1 sequences
    level1_sequences = {}
    for number in range(2, n + 1):
        factors = prime_factors(number)
        for i, factor in enumerate(factors, 1):
            if i not in level1_sequences:
                level1_sequences[i] = []
            level1_sequences[i].append(factor)
    
    # Create Excel file
    wb = Workbook()
    MAX_COLS = 16384
    
    # Function to write sequences to a sheet
    def write_sequences(ws, sequences, prefix):
        current_row = 1
        for seq_num in sorted(sequences.keys()):
            ws.cell(row=current_row, column=1, value=f"Sequence {prefix}{seq_num}")
            for j, number in enumerate(sequences[seq_num][:MAX_COLS-1], start=2):
                ws.cell(row=current_row, column=j, value=number)
            current_row += 1
        
        # Adjust column widths
        ws.column_dimensions['A'].width = 20
        max_width = 1
        for row in ws.rows:
            for cell in row[1:]:
                if cell.value:
                    max_width = max(max_width, len(str(cell.value)))
        for col in range(2, ws.max_column + 1):
            ws.column_dimensions[openpyxl.utils.get_column_letter(col)].width = max_width + 1
    
    # Write original sequences
    ws1_orig = wb.create_sheet("Level1 original")
    ws2_orig = wb.create_sheet("Level2 original")
    
    # Create original level 2 sequences
    level2_sequences_orig = {}
    for i in range(1, len(level1_sequences)):
        if i+1 in level1_sequences:
            result = compare_sequences(level1_sequences[i], level1_sequences[i+1])
            level2_sequences_orig[i] = result
    
    # Write original sequences
    write_sequences(ws1_orig, level1_sequences, "1;")
    write_sequences(ws2_orig, level2_sequences_orig, "2;")
    
    print("\nLevel 1 sequences (original)")
    for seq_num in sorted(level1_sequences.keys()):
        print(f"Sequence 1;{seq_num}: {level1_sequences[seq_num][:50]}")
    
    print("\nLevel 2 sequences (original)")
    for seq_num in sorted(level2_sequences_orig.keys()):
        print(f"Sequence 2;{seq_num}: {level2_sequences_orig[seq_num][:50]}")
    
    # Remove default sheet
    if "Sheet" in wb.sheetnames:
        wb.remove(wb["Sheet"])
    
    # Save file
    script_path = os.path.dirname(os.path.abspath(__file__))
    filename = "results.xlsx"
    full_path = os.path.join(script_path, filename)
    wb.save(full_path)

# Ask user for parameter
n = int(input("Enter a number n: "))
# Execute decomposition
prime_decomposition(n)