시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 0 0 0 0.000%

문제

Mirka je počela zanimati kriptografija pa se bacio na izradu sustava javnog ključa baziranom na „Multiprime RSA“ algoritmu. Detalji sustava nisu bitni za potrebe ovog zadatka, bitno je samo da je važan dio svakog ključa takozvani modul – prirodni broj koji je umnožak dva ili više različitih prostih brojeva. Za sigurnost sustava nužno je (mada možda ne i dovoljno) da se modul teško može rastaviti na proste faktore u nekom normalnom vremenu.

Kako je Mirko neiskusan, pogriješio je već u prvom koraku – generiraju slučajnih prostih brojeva. Naime, njegov generator nema dovoljno entropije pa može generirati ukupno samo 36 različitih prostih brojeva, nadalje svaki generirani prosti broj je manji od 109 . Dakle, svaki modul kojeg Mirko generira je umnožak nekih od tih 36 prostih brojeva.

Mirko je generirao N različitih modula te zamolio prijatelja Slavka da mu pomogne testirati sigurnost tako da proba sve module do kraja rastaviti na proste faktore. Vješti Slavko, koji zna ograničenja Mirkovog generatora, ne samo da će ih sve potpuno rastaviti, nego i želi Mirku dojaviti faktorizaciju na što efikasniji način.

Slavko će Mirku, kao odgovor na njegov izazov, poslati takozvani dokaz faktorizacije - skup prostih brojeva sa svojstvom da, kada se svaki modul podjeli sa svim prostim brojevima iz dokaza (sa kojima je djeljiv) kao rezultat se dobije ili broj jedan ili neki prosti broj. Kako Mirko zna faktorizaciju, kada primi od Slavka dokaz, može se lako uvjeriti da je Slavko stvarno uspio do kraja rastaviti sve module.

Napišite program koji će na temelju niza od N različitih modula odrediti kolika je veličina najmanjeg dokaza faktorizacije. Primjetite da nije potrebno odrediti same proste brojeve u tom dokazu – samo nas zanima koliko ih je najmanje potrebno. 

입력

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100 000), broj modula u Mirkovom izazovu Slavku. U sljedećih N redaka nalaze se prirodni brojevi Xi (2 ≤ Xi ≤ 1018), moduli koje Mirko šalje Slavku.

Svaki Xi je umnožak dva ili više različitih prostih brojeva manjih od 109 . Ukupan broj prostih brojeva koji se pojavljuju kao faktori je najviše 36. 

출력

U prvi i jedini redak izlaza potrebno je ispisati veličinu najmanjeg dokaza faktorizacije. 

예제 입력

2
35
77

예제 출력

1

예제 입력 2

3
6
35
77

예제 출력 2

2

예제 입력 3

1
999992936000441063

예제 출력 3

1

힌트

35 = 5*7, 77 = 7*11. Lako je primjetiti da je potreban samo jedan prosti broj kao dokaz faktorizacije, i to broj 7. Dijeljenjem s njime, ulazni moduli se pretvaraju u { 5, 11 } što su oba prosti brojevi.