Ератостеново сито - квиз¶
- Када проверавамо прималност малог броја малих бројева.
- Када проверавамо прималност малог броја умерено великих бројева.
- Када проверавамо прималност великог броја малих бројева.
- Када проверавамо прималност великог броја умерено великих бројева.
Q-13: У ком случају се највише исплати формирање Ератостеновог сита?
- 1 : 1
- 30 : 1
- 1000 : 1
- 1000000 : 1
Q-14: Нека је потребно да се за око \(100~000\) бројева величине до милион одреди који од њих су прости. Алгоритам A проверава прималност сваког броја појединачно, а алгоритам B формира и користи Ератостеново сито. Процените приближно однос времена извршавања алгоритама A и B.
- Може, без модификација
- Може, ако уместо логичких вредности у низу памтимо целобројне индикаторе простих бројева.
- Може, ако уместо логичких вредности у низу за сваки индекс памтимо један делилац тог индекса.
- Не може.
Q-15: Да ли Ератостеново сито може да се искористи за факторизацију великог броја бројева?