07. Arrays / 10. Prime numbers


0

Здравейте, някой дали може да даде идея как да си оптимизирам кода, защото на половината тестове дава Time limit. т.е в bgcoder дава 50 т

function Prime_numbers(args) {
     let array_prime = [];
     let n = +args;
     let sqrtN = Math.sqrt(n);
     let max_prime_number = 2;

     for (let i=2; i<=sqrtN; i++){
          if(array_prime[i] == undefined){
               let j=i*i;
               while (j<=n){
                     array_prime[j] = true;
                     j += i;
               }
          }
     }
     for (let i=n; i>=2; i--){
          if (!array_prime[i]) {
               return +i;
          }
     }
}




Отговори



0

С алгоритъма на Ератостен изкарах 70/100 т. Просто оптимизирах леко инициализирането на масива и пренебрегнах четните числа без 2. Вместо да го иниц. с true  го оставям undefined . Сигурно има още оптимизации, но нямам повече време за губене. И без това сме претрупани с домашни. Ето го и кода:

/**
* Created by Kalo on 8.1.2017 г..
*/
function solve(args) {
var numN = +args[0],
arr,
temp = +0;
arr = new Array(numN + 1);

for (let j = 3; j <= numN; j = j + 2) {
if (arr[j] === undefined) {
temp = j + j;

while (temp <= numN) {
arr[temp] = 0;
temp = temp + j;
}
}
}

for (var k = numN; k >= 2; k = k - 1) {
if (arr[k] === undefined && arr[k] % 2 !== 0) {
console.log(k);
break;
}
}
}

от Pamir (30 точки)


1

Споделям решение  за 100 точки 

function solve(args) {
    var N = parseInt(args[0]);

    for (var i = N; i > 1; i -= 1) {
        var is_prime = true;
        for (var j = 2; j < i; j +=1) {
            if (i%j === 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            return i;
        }
    }
}




0
Благодаря за решението, въпреки че не използва същия алгоритъм, който е посочен в условието

от Nikra (0 точки)


0

Някой успя ли да оптимизира кода да не гърми bgcoder с Time limit... Поствам и моето решение, макар че половината тестове са Time limit.

function solve(args) { let n = +args[0], array = new Array(n + 1), upperLimit = Math.sqrt(n); for (let i = 2; i <= upperLimit; i += 1) { for (let j = i * i; j <= n; j += i) array[j] = false; } for (let i = n; i => 2; i -= 1) { if (array[i] === undefined) { console.log(i); break; } } }


от p.bonev (0 точки)


1

100/100 решението ми. Тъй като от нас се иска само последното число, тръгва от него назад с loop, вътре върти още един loop до корен от числото(тъй като повече няма смисъл) и когато след вътрешния цикъл prime остане true, връща числото и спира. Малко чийтинг тъй като не се ползва алгоритъма, but oh well

function solve(args) { var number = +args[0]; for(var i = number; i >= 2; i -= 1) { var prime = true; for(var j = 2; j <= (Math.sqrt(i) | 0); j += 1) { if(i % j === 0) { prime = false; } } if(prime) { return i; } } }


от vixataaa (5 точки)