How can I find the Greatest common divisor of two integers

Question

How can I find GCD without using recursion and Euclidian formula? I need to use functions and loops

Answer 1

By testing integer divisibility by primes number and storing those match in a list...

To avoid calculating primes list numbers at each time, set another list with all primes numbers as and when you need them. Test for divusibility by all primes lighter or equal to the square root of your number to decompose is also enough ^^

Answer 2

Sounds like it's an homework assignment: try by yourself first, and ask for specific help about where you get blocked, with posting your code attempt ^^

Anyway, first track to follow, is to be able to decompose integers by prime numbers ;P

Answer 3

Prime numbers are defining by being divisible without reminder (rest of division) only by themselve (and obviously by 1)...

Take 42: it can be integer divided at least by 2, so it's not prime... 2 is as it can be only divided by 1 and 2... next first primes are 3, 5, 7, 11...

To get GCD of 2 integers, you have to decompose them in primes multiplication: always for 42, you will obtain:

42 == 2*3*7

GCD of 42 and another integer would be the common shared primes multiplication. Take 12 as second number, you will have:

12 == 2*2*3

... shared primes are 2 and 3, so GCD of 42 and 12 is 2*3 == 6

Answer 4

( Sorry to be late, but real life was called me ^^ )

This is not as bad for a first step ;)

Some remarks:

> your idea to test if user entry is valid is good, but we'll see later how to improve this task...

> what are you expected with the line 'debugger;'?

> your primeNum() basis seems good, but don't implement what I'm meaning by storing all primes in an array :P

> your final 'if' statement only test if an unique value is prime, and store only once in case of prime number... not at all decompose user number entry... ( as well as you need a second user number entry to calculate GCD of both ^^

Let define the primeNum() function outside of your first 'if' statement ( and anyway fix the missing closing parenthesis -- rounded bracket ), with some fix, improvement and implementation of array to store primes:

https://code.sololearn.com/WPXD8LSoeiIL/#js

Now, we have a function wich populate our primes array as long as we test already untested number.
You can test it with any number, after what, primes array will be filled with all primes number required to be tested for testing primarity of parameter:

var primecount = 10;
var isprime;
for (var test = primes[primes.length-1]; primes.length<primecount; test++) {
isprime = primeNum(test);
isprime = (isprime)?'':' not'; // ternary operator, shorthand for if (isprime==true) { isprime='' } else { isprime=='not' }
console.log(test+' is'+isprime+' prime number');
}
alert('List of primes number stored:\n\n'+primes.join('; '));

Try to implement the GCD function: it should expect 2 integer values, test for each divisibility by primes number...
If it's divisible (no reminder), push the prime to the number decomposed array and divide the number by the pushed last prime tested and continue with the result until result is prime...
Next, you have to put shared items between the two resulting arrays , and do the product of them to have the GCD ;)

I will try to help you deeper tomorrow (in France it's 3:30am) if you doesn't succeed by yourself ^^

Answer 5

It's more simple and quick for me to write the code than help you to do it yourself, but I will not help you by this way :P

I repeat from my first answer:
<< Sounds like it's an homework assignment: try by yourself first, and ask for specific help about where you get blocked, with posting your code attempt ^^ >>

Answer 6

I realize now, working on next steps for implementation of GCD, that I've used recursion in my primeNum() implementation, while you ask "without recursion"... but recursion is useful for improve the code, and since you don't have good reasons to avoid it (you never have recognized that's an homework assignment, so I doesn't see why avoid it :P), I let it as is, but we can adapt it in a less improved way to avoid it ^^

Anyway, I guess I will post the complete solution soon ;)

Answer 7

Done!

Should I publish the second (and last) step of the GCD tutorial now, or wait for your attempt? ;P

...

...

...

Well, too bad for you if you doesn't try by yourself before look at it, it's not my problem after all ^^

https://code.sololearn.com/WteKxMC4vDvC/#js

( all explanations are inside code as comments: ask for more if not enough, but today I will not be very available for some long hours to be on the road, driving my car, after what I will need some rest before going to hard work, letting me very few available for days to come up :P )

Answer 8

I just can't figure out how to find all the prime divisors of an integer.Should I use a for loop?

Answer 9

I know the definition of prime numbers, common divisor and all that jazz.The problem is I cannot put it into code, like var int=prompt("insert a number"), how do I find the product of prime divisors for a certain number?

Answer 10

Could you bring an example.I am a complete beginner and didn't get you.Will be thankful

Answer 11

OK.

So here I need to put all the prime divisors in the array

var a = parseInt(prompt("please write a number"));
var p=[];

if(!isNaN(a)&& a > 1){
debugger;
function primeNum(num{
var s =Math.round(Math.sqrt(a));
for(var i = 2;i<=s;i++){
if (a % i === 0) {
return false;
}
}
return true;
}

if(primeNum(a)==true) {
p.push(a);
alert(p);
} primeNum()
}

Answer 12

I am really thankful for your feedback. Very helpful.