daa_project.py

# -*- coding: utf-8 -*-
"""DAA_project.ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/1UCVczZvmbBNMc3mH2cKZs-8kvn2iYpMJ
"""

import secrets
import random

# Colors
RED = "\033[91m"
GREEN = "\033[92m"
CYAN = "\033[96m"
RESET = "\033[0m"

# List to store probable primes
probable_primes = []

# 1) Sieve of Eratosthenes
def sieve(limit):
    if limit < 2:
        return []
    arr = bytearray(b'\x01') * (limit + 1)
    arr[0:2] = b'\x00\x00'
    for p in range(2, int(limit**0.5) + 1):
        if arr[p]:
            arr[p*p : limit+1 : p] = b'\x00' * ((limit - p*p)//p + 1)
    return [i for i, isprime in enumerate(arr) if isprime]

# 2) Miller-Rabin Test
def is_probable_prime(n, k=12):
    if n < 2:
        return False
    small_primes = [2,3,5,7,11,13,17,19,23,29]
    for p in small_primes:
        if n % p == 0:
            return n == p
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = secrets.randbelow(n - 3) + 2
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# ----- Option 1: Single Number -----
def check_single_number(small_primes):
    try:
        user_input = int(input(CYAN + "Enter a number to test for primality: " + RESET))
    except ValueError:
        print(RED + "Invalid input! Enter an integer." + RESET)
        return

    for p in small_primes:
        if user_input % p == 0 and user_input != p:
            print(RED + f"{user_input} is divisible by {p} → NOT prime." + RESET)
            return

    if is_probable_prime(user_input):
        print(GREEN + f"{user_input} PASSED Miller-Rabin → Probably Prime" + RESET)
        probable_primes.append(user_input)
    else:
        print(RED + f"{user_input} FAILED Miller-Rabin → Composite" + RESET)

# ----- Option 2: Range -----
def check_range(small_primes):
    try:
        start = int(input(CYAN + "Enter start of range: " + RESET))
        end = int(input(CYAN + "Enter end of range: " + RESET))
    except ValueError:
        print(RED + "Invalid range! Integers only." + RESET)
        return

    if start > end:
        print(RED + "Start cannot be greater than end!" + RESET)
        return

    for num in range(start, end + 1):
        divisible = False
        for p in small_primes:
            if num != p and num % p == 0:
                print(RED + f"{num} → divisible by {p} → Composite" + RESET)
                divisible = True
                break
        if not divisible:
            if is_probable_prime(num):
                print(GREEN + f"{num} → Probably Prime" + RESET)
                probable_primes.append(num)
            else:
                print(RED + f"{num} → Composite" + RESET)

# ----- Option 3: Random Number -----
def check_random_number(small_primes):
    try:
        lower = int(input(CYAN + "Enter lower bound: " + RESET))
        upper = int(input(CYAN + "Enter upper bound: " + RESET))
    except ValueError:
        print(RED + "Invalid bounds! Enter integers only." + RESET)
        return

    if lower > upper:
        print(RED + "Lower cannot be greater than upper!" + RESET)
        return

    random_num = random.randint(lower, upper)
    print(f"Generated: {random_num}")

    for p in small_primes:
        if random_num % p == 0 and random_num != p:
            print(RED + f"{random_num} → divisible by {p} → Composite" + RESET)
            return

    if is_probable_prime(random_num):
        print(GREEN + f"{random_num} → Probably Prime" + RESET)
        probable_primes.append(random_num)
    else:
        print(RED + f"{random_num} → Composite" + RESET)

# ----- Save to file -----
def save_primes_to_file():
    if not probable_primes:
        print(RED + "No probable primes found to save." + RESET)
        return
    with open("probable_primes.txt", "w") as file:
        for prime in probable_primes:
            file.write(str(prime) + "\n")
    print(GREEN + f"Saved {len(probable_primes)} probable primes to 'probable_primes.txt'." + RESET)

# ----- Main Flow -----
def main():
    print("Generating primes (sieve) up to 100,000...")
    small_primes = sieve(100000)
    print(f"Total primes generated: {len(small_primes)}")

    while True:
        print("\n------- MENU -------")
        print("1. Check a single number")
        print("2. Check a range")
        print("3. Generate & test a random number")
        print("4. Save probable primes to file & Exit")

        choice = input(CYAN + "Enter your choice (1-4): " + RESET)

        if choice == "1":
            check_single_number(small_primes)
        elif choice == "2":
            check_range(small_primes)
        elif choice == "3":
            check_random_number(small_primes)
        elif choice == "4":
            save_primes_to_file()
            print(GREEN + "Exiting..." + RESET)
            break
        else:
            print(RED + "Invalid choice! Pick 1-4." + RESET)

if __name__ == "__main__":
    main()