Как е този код, който идентифицира първите числа [затворен] - java, primes

Това е кодът, който идентифицира прости числа до даденото число. Ако въведете, да речем 7, върнатият ArrayList ще има всички първи 7 прости числа в него.

    public static ArrayList<Integer> calcPrime(int inp)
{
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(2);
arr.add(3);

int counter = 4;

while(arr.size() < inp)
{
// 23 and 25
if(counter % 2 != 0 && counter%3 != 0)
{
int temp = 4;
while(temp*temp <= counter)
{
if(counter % temp == 0)
break;
temp ++;
}
if(temp*temp > counter)
{
arr.add(counter);
}
}
counter++;
}

return arr;
}

Въпросът ми е това. Разбирам, че този код филтрира всички числа, които се делят на 2 и 3. Но за всички останали числа, да речем 23 или 25, той просто разчита на квадратите от числа от 4.

Искам да знам как това постига целта си. Моля, помогнете ми да разбера това.

Отговори:

2 за отговор № 1

Битът, който прави проверката, е следният:

                if(counter % temp == 0)
break;

Всъщност изобщо не разчита на квадратите от числа. Това просто го казва кога да спре да проверява числата.

Първо прави някаква първоначална настройка. Знае, че 2 и 3 са прайдове, затова ги добавя към списъка си.

След това, започвайки от 4, той проверява дали числото е основно. Ако е, той го добавя към масива, ако не е, той пропуска и проверява следващото число.

Така че „Проверка, за да се види дали числото е първостепенно“ се извършва от: първо проверете дали е делимо на 2 или делимо на 3:

    if(counter % 2 != 0 && counter%3 != 0)

След това, започвайки отново в 4, правя същата проверка: Моят потенциален премиер (counter) делимо на това число (temp);

        if(counter % temp == 0)

Ако това е така, това не е просто число, така че това е break командва и проверява следващия counter за да видим дали това е премиер.

ако counter не се дели на temp той нараства temp и проверява отново. Кога temp е толкова голям, че не си струва да се проверява дали вече е фактор, алгоритъмът знае това counter е премиер и го добавя към списъка.

Най- temp*temp бит е, защото когато се проверява дали дадено число е първостепенно, не е необходимо да проверявате всички числа до counter, ако temp*temp е по-голяма от нашата цел, тогава за temp за да бъде фактор, другият фактор трябва да е по-малък от temp, и той вече е проверен.

---

0 за отговор № 2

% означава остатък, когато е разделен на, и фрагментът върши действителната работа. Ако остатъкът е нула, тогава той се дели точно, така че числото не е просто.

Квадратната част е, защото можете да оптимизирате малко, като вземете предвид числата, по-малки от квадратния корен (защото, ако число, по-голямо от квадратния корен, се дели, резултатът е по-малко отколкото квадратния корен и би трябвало да е хванат по-рано)

---