JS - Module 0 - Biggest Prime Number

Здравейте!
При решението на задачата описана по-долу излиза Memory Limit Exceeded и получавам 40 точки.

Бихте ли ме насочили?

Write a program that finds all prime numbers in the range 1 ... N . Use the Sieve of Eratosthenes algorithm. The program should print the biggest prime number which is <= N .

1 Like

Здравей, проблемът ти се получава от първият for(){} loop на 5ти ред, накратко той минава през абсолютно всички числа от 2 до n-1 и ако числото например 926204 той ще направи 926201 цикъла погледни дали и на други места може да се получи така. Вместо това използвай let arr = new Array(n); (създава array с n елемента всички празни, пробвай array.lenght() за да се увериш) и след това arr.fill(true) (това запълва в случая всички елементи с true и веднага след променяме arr[0] и arr[1] в false). Виждам, че и в следващият for(){} loop с голями числа се получават много сметки. Весели празници!

Здравей!

Благодаря ти за съвета… В резултат на него разрах и направих следното:

Вече имам 50 точки, но явно пак пропускам нещо. Чудя се дали не е в логиката на моето решение.

Погледнах го отново не съм прочел правилно мислех че проблемът е Time Limit Exeeded (често ми се случва и по навик). Проблемът е от arr, създават всички елементи от 2 до n и това пълни памета. Не е твоята логика кадето е грешна а самата Sieve of Eratosthenes която не е много за тази задача след като изисква създаването на тези елементи в arr, но judge има лимит на памета и там се получава проблемът.

1 Like

А, защо не търсиш най-голямото просто число започвайки от N? Струва ми се, че така ще го намериш с по-малко стъпки.

Да, би могло, но условието е написано така:

Write a program that finds all prime numbers in the range 1 ... N . Use the Sieve of Eratosthenes algorithm. The program should print the biggest prime number which is <= N .

1 Like

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

1 Like