Тест прималности - квиз¶
- Број n има 1 или више сложених делилаца мањих од 1000.
- Број n има 1 или више (нетривијалних) простих делилаца већих од 1000.
- Број n има 1 или више сложених делилаца већих од 1000.
- Број n је дељив тачно једним простим бројем.
Q-3: Нека је природан број n мањи од милион и нема простих делилаца мањих од 1000. Шта од наведеног може да важи за број n (означити све тачне одговоре)?
- Ни за један број.
- Само за број a.
- Само за бројеве a и b.
- За сва три броја.
Q-4: Нека је \(a=222~222~222~222~222~222\), \(b=333~333~333~333~333~333\), \(c=555~555~555~555~555~555\). Лако се види да је број \(a\) дељив са 2, број \(b\) са 3, а број \(c\) са 5. Ако би последњи дати (најбржи) алгоритам проверавао прималност ових бројева, за које од њих би могао да да одговор после свега неколико (нпр. мање од 20) операција?
- око 40
- око 1000
- око 300 000
- око 1 000 000 000 000
Q-5: Колико итерација је потребно последњем датом (најбржем) алгоритму у најгорем случају, да за било који број из интервала \([1, 1~000~000~000~000]\) провери да ли је тај број прост?
- око 1000 секунди
- око 1 секунде
- око 30 милисекунди
- око 10 милисекунди
Q-6: Нека је последњем датом (најбржем) алгоритму у најгорем случају потребно око 1 милисекунде да за било који број из интервала \([1, n]\) провери да ли је тај број прост. Колико је времена у најгорем случају потребно истом алгоритму да за било који број из интервала \([1, n \cdot 1~000~000]\) провери да ли је тај број прост?