1316 - Prim Aproape Prim - Patrat Prim - Compus

Cerinţa

• Un număr natural nenul este prim, dacă are exact doi divizori (ex. 7).
• Un număr natural nenul se va numi pătrat prim, dacă este pătratul unui număr prim (ex. 49 = 7 * 7).
• Un număr natural nenul se va numi aproape prim, dacă este produsul a două numere prime distincte (ex. 10 = 2 * 5).
• Un număr natural nenul ce nu se încadrează în niciuna din cazurile de mai sus, se numeşte compus (ex. 8=2*2*2, 100=2*2*5*5).

Se citeşte un număr natural n. Să se identifice din ce categorie de mai sus face parte.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul va afișa pe ecran unul dintre mesajele: prim, aproape prim, patrat prim sau compus.

Restricții și precizări

• 1 < n ≤ 2.000.000.000

Exemplu

Intrare

20

Ieșire

compus

Explicație

Numărul 20=2*2*5, deci este număr compus.

Rezolvare

import math

def is_prime(n):
    if n <= 1:
        return False
    elif n == 2 or n == 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    else:
        i = 5
        while i <= math.sqrt(n):
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
        return True

def validare_date(numar1, numar2):
    flag = False

n = int(input())

if n <= 1:
    print("Nu este niciunul dintre tipurile cerute.")
elif n == 2 or n == 3:
    print("prim")
elif n % 2 == 0 or n % 3 == 0:
    print("compus")
else:
    is_prime = True
    i = 5
    while i <= math.sqrt(n):
        if n % i == 0 or n % (i + 2) == 0:
            is_prime = False
            break
        i += 6
    if is_prime:
        print("prim")
    else:
        sqrt_n = math.isqrt(n)
        if sqrt_n ** 2 == n:
            is_prime = True
            i = 2
            while i <= math.isqrt(sqrt_n):
                if sqrt_n % i == 0:
                    is_prime = False
                    break
                i += 1
            if is_prime:
                print("patrat prim")
            else:
                print("compus")
        else:
            found = False
            for i in range(2, math.isqrt(n) + 1):
                if n % i == 0 and is_prime(i) and is_prime(n // i):
                    found = True
                    break
            if found:
                print("aproape prim")
            else:
                print("compus")