Biggest Prime Number

Здравейте, може ли някой да ми обясни защо дава 30/100 като всичко работи?
Условие: https://judge.telerikacademy.com/problem/15primenumbers
Решение:https://pastebin.com/RRxnVbuy

Здравей, kiro671,

Мисля, че отговорът на въпроса ти се съдържа в коментара на pmgeorg1974: https://judge.telerikacademy.com/problem/15primenumbers#comment-657

Загуба на време е да се търсят всички прости числа по-малки или равни на n, когато е необходимо да се намери само най-голямото от тях. Освен това, за да се установи дали едно цяло положително число, q, е просто или не, е достатъчно да се провери дали q има делител, d, такъв че

2 ≤ d ≤ √(q) (квадратен корен от q)

[Ако q има делител s, такъв че √(q) < s < q, то частното d = q/s също ще бъде делител на q, за който ще бъде изпълнено 1 < d < √(q).]

Следователно, цикълът, който проверява дали числото q е просто, може да се напише например така:

int u = (int) Math.sqrt(q);
boolean divisorFound = false;
for (int d = 2; d <= u && !divisorFound; ++d) {
    divisorFound = (q % d == 0);
}

Това също ще съкрати времето, необходимо за изпълнение на програмата.

Поздрави,
Иван

2 Likes

Благодаря много!