Problem 3: Largest prime factor- project euler

Tell us what’s happening:

Your code so far


function largestPrimeFactor(number) {
  // Good luck!

let j=[];
for(var i=2;i<=number;i++){
if(number%i===0)
j.push(i);
}
var counter;
for(var k=0;k<j.length;k++){
     for(counter=2;counter<=j[k]/2;counter++){
       if(j[k]%counter===0){
       var index = j.indexOf(j[k]);
 
       if(index > -1) {
          j.splice(index, 1);
       }
    }
     }
}
var lastItem = j.pop();
  return lastItem;
}

largestPrimeFactor(13195);

Your browser information:

User Agent is: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_4) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.87 Safari/537.36.

Link to the challenge:
https://learn.freecodecamp.org/coding-interview-prep/project-euler/problem-3-largest-prime-factor

Be careful with splicing an array that you’re iterating through. Note that when you splice, the rest of the elements are shifted to the left. This means that after splicing, the element that is supposed to be next in the iteration is skipped over.

It’s hard to put in words, so here’s an illustration. Suppose that you have the array [10, 20, 30, 40, 50, 60, 70] that you want to loop through. The current index is stored in the variable k.

k = 0
[10, 20, 30, 40, 50, 60, 70]
  ^
  this is the current element

Suppose you spliced this out of the array. Now you have:

k = 0
[20, 30, 40, 50, 60, 70]
  ^
  this is _now_ the current element (even though `k` didn't change).

Then the loop increments the k variable:

k = 1
[20, 30, 40, 50, 60, 70]
      ^

Note that 20 above has been skipped.

This is what happens in your for-loop. Some elements are skipped when you splice.

@kevcomedia but i don’t it skipped in the above solution , rather I just kind of remove the items with value j[k] using splice…isn’t that right.
I tried that in the Fcc sonsole and all the scenerios are fulfilled only 13195 has got some problem…oops pls help me out!

You can see it for yourself here: https://repl.it/repls/DeafeningGleamingDictionary. I printed the full j array, and each time the second for-loop begins I’m printing the current number. You’ll see that not all numbers are printed.

what can i rather use in-place of splice any alternative pls?

Instead of removing it entirely with splice, you can just mark it with a special value that you know cannot be a prime factor to mark that it has been “removed” (say, assign it a negative number, since they can’t be prime).

Now at the end the array should contain only either the input’s prime factors, or this dummy value. Now you just have to look for the largest number in the array while ignoring the dummy values.

@kevcomedia this works fine but has hight time and space complexity…
by the way thanks

function largestPrimeFactor(number) {
  // Good luck!
 
let j=[];
for(var i=2;i<=number;i++){
if(number%i===0)
j.push(i);
}
var counter;
for(var k=0;k<j.length;k++){
     for(counter=2;counter<=j[k]/2;counter++){
       if(j[k]%counter===0){
       j[k]=-1;
       }
     }
}
j.sort(function(a, b) {
    return a - b;
  });
  var largest = j[j.length - 1];

  return largest;
}

largestPrimeFactor(13195);

Sorting might not be the way to go if you just need to get the largest number in an array. You can go linear time with that.

do u wanna pair with me in solving these Euler problems…
:wink::face_with_raised_eyebrow:

I’m not focusing on algorithms for the moment, so I’m not sure :thinking:

kk…Happy coding:+1:t2: