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
borislav9212 avatar borislav9212 745 Точки

Ето моето решение н азадачата, може да ти помогне, мисля, че е по разбираемо -> http://pastebin.com/YnDYT5Gz

0
YavorSpassov+deleted! avatar YavorSpassov+deleted! 133 Точки

Не, не ми помогна. Имам същото решение, а условието тук е различно.

0
ralitsa_d avatar ralitsa_d 171 Точки

Здравей, ето моето решение - проверявам числата не от 1 до N, а до корен квадратен от N. Така си спестявам доста излишни проверки.

http://pastebin.com/z8Z34GqP

0
YavorSpassov+deleted! avatar YavorSpassov+deleted! 133 Точки

Здравей,

Интересно решение с използване на метод, но и в твоето, и в решението на borislav9212, първоначално се предполага, че числото е просто.

0
ralitsa_d avatar ralitsa_d 171 Точки

Прдвид това, че имаш while цикъл, ти трябва някакво условие, което да прекъсне цикъла - в случая това става, когато намерим делител на числото - казваме isPrime = false; и брейкваме цикъла.

Ако започнем с число N, за което приемаме, че не е prime, трябва да проверим за всяко число от 2 до N дали е делител на N. Ако не е делител, това все още не означава нищо, защото следващото може да е. Затова можем да си направим една променлива counter, в която да пазим броя на числата, които не са делители на N. Накрая ще сравним counter-а с числата от N-2 и ако са равни, то N е просто число.

Не съм го разписвала като задача, но това решение ми се вижда доста по-дълго и сложно. Вероятно има и други начини, това ми идва на ум на пръв поглед :)

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