Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – algorithm for Prime Factorization

I’m studying algorithm these days,
and I found that my approaching is usually different with others.

I’m self-studying, so I don’t have any kind of mento or teacher.
So I’m having lots of worry about ‘Is this Ok that I am different’.
I’m having enjoying time with studying create some codes,
but I’m not sure I can do that well like others and match my logical structure with others,
these days cause of this kind of question.

Could you please tell me what is my problem exactly and HOW can I resolve or improve myself?

This is a question from some site which for studying coding test.

🌿 Others code( usually people solve this way )

const solution = (n) => {
    var answer = [];
    let curNum = n;
    let count = 2;
    
    while (curNum !== 1) {
        if (curNum % count === 0) {
            answer.push(count)
            curNum = curNum/count
        } else {
            count++
        }
    }
    
    let check = [...new Set(answer)]
    
    return check 
}

🌱 my code

const solution = (n) => {
  let result = n;
  let answer = [];
  const num = [2, 3, 5, 7];
  
  for( let i = 0; i < num.length; i ++ ){
    while( result >= 1 && result % num[i] === 0 ){
      answer.push(num[i]);
      result = result / num[i];

      if( result % num[i] !== 0){ 
        break;
      }
    }
  }  
  if( result !== 1 && Number.isInteger(Math.sqrt(result))) answer.push(Math.sqrt(result));
  else if( result !== 1) answer.push(result);
  
  return [...new Set(answer)].sort(((a, b) => a - b));
}

I solved this problem in this way,
cause I thought if ‘n’ is really big number and if it has lots of Prime factors,
then it will be have lot of repeat,
so first, I try to get rid of which is multiple of [2, 3, 5, 7].
and after that, check the remain is square number or not.

if the remain is square number, then push square root,
if not push the remain.

I heard that ‘nested loop’ is not good for running time( it can be longer ), today.
So I will improve about it more and more.

I want to ask that is it okay this kind of different way with others to solve the problem.

Thank you for reading this long question.

Tags:

2

Answers


  1. 0

    Your proposed code does not always correctly return the input’s prime factors.

    1. The program can never return more than five prime factors (four in the loop, and one more at the end). Yet it is clear there are integers that have more than five prime factors.

    2. Your code assumes that if after the loop result is still non-prime, it must be a perfect square. This is for instance not true with 143, which is not prime and not a perfect square either. It should be broken down into factors 11 and 13, but your code does not detect those factors, and returns the non-prime 143.

    3. On the other hand, if after the loop result happens to be a perfect square, this program wrongly assumes that its square root will be a prime. For instance 14641 is a perfect square of 121, but 121 is not a prime. Yet your code will return that as the prime factor, while it should return 11 as prime factor.

    Back to the drawing board.

    Login or Signup to reply.
  2. 0

    When integer number n is prime? Two conditions should be met:

    1. n > 1
    2. n <> p * q where p > 1 and q > 1

    Let’s have a close look at n <> p * q, let p <= q (we can swap p and q).
    In the edge case, when p == q we have n = p * p or p = sqrt(n). So far so good,
    we should check all potential divisors in 2..sqrt(n) range.

    We can optimize this check – we can try p = 2 and the odd ps only:

    const solution = (n) => {
    var answer = []
 
    if (n <= 1) 
        return answer

    for (; n % 2 == 0; n /= 2) 
        answer.push(2)

    let limit = Math.ceil(Math.sqrt(n))

    for (let d = 3; d <= limit; d += 2) {
        for (; n % d == 0; n /= d) {
            answer.push(d) 
            limit = Math.ceil(Math.sqrt(n))
        }
    }

    if (n > 1)
        answer.push(n)

    return answer
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search