def lucas_lehmer_test(p):
    # s = 4
    # repetăm de (p-2) ori:
    #   s = (s^2 - 2) mod (2^p - 1)
 
    s = 4
    M_p = (2**p) - 1
 
    for i in range(p - 2):
        # AICI este punctul critic! s*s este o înmulțire de numere gigantice.
        # Trebuie să folosim FFT pentru a calcula s^2.
        s = (s * s - 2) % M_p
 
    if s == 0:
        return "PRIM GĂSIT! (150.000$ sunt ai tăi)"
    else:
        return "Compus"

ZGVmIGx1Y2FzX2xlaG1lcl90ZXN0KHApOgogICAgIyBzID0gNAogICAgIyByZXBldMSDbSBkZSAocC0yKSBvcmk6CiAgICAjICAgcyA9IChzXjIgLSAyKSBtb2QgKDJecCAtIDEpCiAgICAKICAgIHMgPSA0CiAgICBNX3AgPSAoMioqcCkgLSAxCiAgICAKICAgIGZvciBpIGluIHJhbmdlKHAgLSAyKToKICAgICAgICAjIEFJQ0kgZXN0ZSBwdW5jdHVsIGNyaXRpYyEgcypzIGVzdGUgbyDDrm5tdWzIm2lyZSBkZSBudW1lcmUgZ2lnYW50aWNlLgogICAgICAgICMgVHJlYnVpZSBzxIMgZm9sb3NpbSBGRlQgcGVudHJ1IGEgY2FsY3VsYSBzXjIuCiAgICAgICAgcyA9IChzICogcyAtIDIpICUgTV9wCiAgICAgICAgCiAgICBpZiBzID09IDA6CiAgICAgICAgcmV0dXJuICJQUklNIEfEglNJVCEgKDE1MC4wMDAkIHN1bnQgYWkgdMSDaSkiCiAgICBlbHNlOgogICAgICAgIHJldHVybiAiQ29tcHVzIg==