Write a function to take a positive integer and a prime number as an input and return true if the prime factors of the given positive integer are less than the given prime number

JavaScript
1

Write a function to take a positive integer and a prime number as an input and return true if the prime factors of the given positive integer are less than the given prime number

Example :

hasLessPrimeFactor(20,5) should return true because Prime Factors of a Number: 20 = 2 X 2 X 5

**I have implemented following JS code for above question. But it has some error. **
Appropriate if anyone can help me.

function checkPrime (i){
  let isPrime = true;
      for (let j = 2; j <= i / 2; j++) {
        if (i % j == 0) {
          isPrime = false;
        }else{
          isPrime = true;
        }
      }
      return isPrime;
}
function hasLessPrimeFactor(value, primenum) {
  let returnValue = false,
      number = value,
      primeArray = [1];
  
  for (let i = 2; i <= number/2; i++) {
    if (number % i == 0) {
      let isPrime = checkPrime(i);
      if (isPrime){ 
        number /= i;
        primeArray.push(i);
      }
    }
  }
  if(checkPrime(value)){
    primeArray.push(number);
  }
  if (primeArray[primeArray.length-1] >= primenum){
    returnValue = true;
  }
  return returnValue;
}
2

Some things to note:

You don’t need to find out all the prime factors of the positive integer, just the largest of them (think why this is)

Your for loop does too many iterations, you only need to go to the square root of i (think about why this is), and you don’t need to check every even number except 2 (so change to i += 2 in the loop section)

If this is for Project Euler and the like, then it’s worth investing in a good prime number generator of some form. See the following paper for my favourite version of the Sieve of Eratosthenes: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf or search online for various others

Note that the code is written in Haskell, however one can rewrite it using javascript generators if they’re daring

1 Like
3

Thanks for your note. I’ll try with that.