CODEWITHSUNDEEP
javascript
Vodka_Tonic
Vodka_Tonic

Reputation: 152

Checking for a Prime Number with JavaScript

I'm doing the 3rd project euler question right now. So far I've figured out how to solve the problem which is finding the largest prime factor of 600851475143.

I've wrote a small bit of code that can place all the prime factors of a number into an array. The problem I'm having is the number may be too large to compute. I've used other large numbers (not as large as this one) and they've worked fine but this one just freezes up the page like it's in an endless loop. Here's the code: 

var primes = [];
function factor (largestNumber) {
    var a = largestNumber;
    var b = 2; 
    while (b < largestNumber) {
        if (a % b == 0) {
            a /= b;
            primes.push(b);
            b = 2;

        } else {
            b++;
        }
    }
}

factor(600851475143);
console.log(primes);

Upvotes: 1

Views: 208

Answers (2)

Tyler.z.yang
Tyler.z.yang

Reputation: 2450

This may be a useful way, split the largest primary factor into 3 part.

  1. Cut the largest Num into 2 close num eg 40 => 5 * 8

  2. Get the bigger num(8) and find out all the prime num small than it. Storage into Array.

  3. Use a loop to get the largest prime factor.

That's all, I will try it tonight. If I make it I will add the jsfiddle addr. : )

Upvotes: 0

sectus
sectus

Reputation: 15464

Your algorithm is not optimal.

function factor(largestNumber) {
    var primes = [];                          // using local value
    var a = largestNumber;
    var b = 2;
    while (b <= Math.floor(Math.sqrt(a))) {   // we do not need to check whole number
                                              // over and over again.
                                              // We could check to a only 
                                              // or even to sqrt(a) only
        if (a % b == 0) {
            a /= b;
            primes.push(b);
                                             // there is no reason to reset value
        } else {
            b++;
        }
    }
    primes.push(a);                          // rest number would be always prime
    return primes;
}

console.log(factor(600851475143));

Upvotes: 2

Related Questions