########################################################################
## 2. prednaska                                                       ##
## For cykly, pole a prace s nimi, modul Math, Eratosthenovo sito     ##
########################################################################

import math


# Vypise vsechny delitele cisla nacteneho ze vstupu
def delitele():
    cislo = input()
    for delitel in range(1, cislo+1):
        #a = math.floor(cislo / delitel)
        #if a * delitel == cislo:
        if cislo % delitel == 0:
            print delitel


# Spocita pocet delitelu cisla
# Bezi v case O(n)
def pocet_delitelu(cislo):
    pocet = 0
    for delitel in range(1, cislo+1):
        if cislo % delitel == 0:
            pocet += 1
    return pocet


# Trivialni implementace provocisel, prvocislo ma jen dva delitele (1 a sebe samo)
# Bezi v case O(n*n) -- pro kazde cislo pocita v case O(n) pocet delitelu
def prvocisla_trivial(max):
    for i in range(2, max+1):
        if pocet_delitelu(i) == 2:
            print i, "je prvocislo"


# Eratosthenovo sito na prvocisla
# 1. Prvni cyklus vygeneruje pole plne nul
# 2. Potom pro kazde doposud nevyskrtnute cislo vyskrtneme z pole vsechny
#    jeho nasobky
# 3. Nakonec pole zase jednou precteme a vypiseme
# Bezi v case O(n log log n)
def eratostenes(horni_mez):
    tabulka = []
    prvocinitele = []

    for i in range(0, horni_mez):
        tabulka.append(0)
        prvocinitele.append([])

    for i in range(2, horni_mez):
        if tabulka[i] == 0:
            for j in range(i * 2, horni_mez, i):
                tabulka[j] = 1  # J neni prvocislo, protoze je delitelne I.
                prvocinitele[j].append(i)  # I je jeho prvocinitel, protoze I je prvocislo.

    for i in range(2, horni_mez):
        if tabulka[i] == 0:  # I je prvocislo
            print i, "je prvocislo"
        else:
            print i, "neni prvocislo, deli ho tyhle prvocisla:", prvocinitele[i]


# Obrati pole tak, ze postupne odzadu vklada prvky stareho pole do pole vysledek
def obrat(pole):
    vysledek = []
    for i in range(len(pole)):
        vysledek.append(pole[len(pole) - i - 1])
    return vysledek


def main():
    prvocisla_trivial(100)
    eratostenes(100)


# Rozdil oproti prvni prednasce:
# Toto je "bezpecnejsi" volani funkce main(). Ta se provede jen, pokud je skript
# spusten samostatne, pokud je importovan prikazem "import", tak se nic neprovede
if __name__ == '__main__':
    main()