Loading...
YavorSpassov+deleted! avatar YavorSpassov+deleted! 133 Точки

Check prime from Advanced loops exercises

Имате ли решение на задачата, в което, вместо да приемате от подсказката, че всяко число е просто, приемате, че по подразбиране не е? Доколкото разбрах, на изпита няма да има подсказки. Което за мен означава, че е по-добре да си изработим своя собствена логика за всяка задача.

Условие: https://judge.softuni.bg/Contests/Practice/Index/156#9

Моето решение: http://pastebin.com/fiuM0c3Y

Единственият проблем тук, е че на тест номер 14 връща Time Limit и резултатът е 94%. Тоест, някой може да не получи стипендия, ако ползва това решение. Как да му помогнем?

 

0
Programming Basics
KrasimirPetkov avatar KrasimirPetkov 328 Точки
Best Answer

Здравей,

При проверките за това, дали едно число N е просто или не, често се използва цикъл не до самото число N, а до корен квадратен от него. Така се решава проблемът с Time Limit.

Защо се използва корен квадратен? Нека да видим пример с 64.

64 = 8х8

64 = 4х16

64 = 2х32

Ще забележиш, че както и да представяме 64, само при 8х8 (корен квадратен от 64), двете числа са равни - във всички други случаи, поне едно от числата е по-малко от 8. Това означава, че ако числото не е просто, то ще преминем през някой негов делител, ако обходим само стойностите до корен квадратен от самото число. Във всички други случаи, се правят излишни проверки.

Ето и решение на задачата (добавил съм и коментари): http://pastebin.com/6NEiCY98

1
30/06/2016 15:29:31
YavorSpassov+deleted! avatar YavorSpassov+deleted! 133 Точки

От гледна точка на проверките, твоето решение е по-изчистено и по-добро. Добре е, че си съобразил, че всички четни числа (по-големи от 2) имат повече от един делител и следователно проверката за тях е излишна. Тоест, те не са прости.
Нямаше да се сетя да ползвам и следното условие: i <= Math.Ceiling(Math.Sqrt(n))
С методи още не работим в Programming Basics, затова махнах твоя в новото решение и се опитах да го адаптирам по моята логика: http://pastebin.com/M7azQXk5

Въпреки, че прави повече и излишни проверки, моето решение остава по-интуитивно за мен.

1
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.