Whith this code , with the first loop in comment and with only one number passed in argument that works.:
function smallestCommons(n) {
//let max = Math.max(...arr);
//let min = Math.min(...arr);
//console.log(min)
const dividedBy = [[],[]]
//for (let n = min; n <= max; n++) {
/* I don't want to iterate over all the numbers so I'm only looking for prime numbers like in the previous exercise*/
//________________________________________________________________
let maxMultiple = Math.floor(Math.sqrt(n));
let numbers = [];
for (let l = 2; l <= n; l++) {
numbers.push(l);
}
for (let i = 2; i <= maxMultiple; i++) {
for (let j = Math.pow(i, 2) ; j <= n; j += i) {
if ( j !== false) {
numbers[j - 2] = false;
}
}
}
//console.log(numbers)
let primes = numbers.filter(item => Number.isInteger(item));
//_________________________________________________________________
primes.unshift(0,0)
console.log(primes)
let compte = 0;
dividedBy.push([0,0]);
console.log(dividedBy)
for (let k = 2; k <= primes.length; k++) { //for each number n in the first for loop, I decompose over each prime number.
if (n % primes[k] == 0) {
let n2 = n / primes[k];
compte += 1
n = n2;
k--;
}else{
dividedBy[dividedBy.length-1].push(compte)
compte = 0
}
}
console.log(dividedBy)
//}
}
smallestCommons([18]);
For smallestCommons([18]) the console return:
Great!!
But when I add the first for loop, with smallestCommons([9,18]) there is a infinity loop:
function smallestCommons(arr) {
let max = Math.max(...arr);
let min = Math.min(...arr);
console.log(min)
const dividedBy = [[],[]]
for (let n = min; n <= max; n++) {
/* I don't want to iterate over all the numbers so I'm only looking for prime numbers like in the previous exercise*/
//____________________________________________________________________
let maxMultiple = Math.floor(Math.sqrt(n));
let numbers = [];
for (let l = 2; l <= n; l++) {
numbers.push(l);
}
for (let i = 2; i <= maxMultiple; i++) {
for (let j = Math.pow(i, 2) ; j <= n; j += i) {
if ( j !== false) {
numbers[j - 2] = false;
}
}
}
//console.log(numbers)
let primes = numbers.filter(item => Number.isInteger(item));
//__________________________________________________________________
primes.unshift(0,0)
console.log(primes)
let compte = 0;
dividedBy.push([0,0]);
console.log(dividedBy)
for (let k = 2; k <= primes.length; k++) { //for each number n in the first for loop, I decompose over each prime number.
if (n % primes[k] == 0) {
let n2 = n / primes[k];
compte += 1
n = n2;
k--;
}else{
dividedBy[dividedBy.length-1].push(compte)
compte = 0
}
}
console.log(dividedBy)
}
}
smallestCommons([9,18]);
To try to find what is causing infinite loop, you may take a look at loops one-by-one. Double check the stopping condition, and if variables are changed in such way, that loop will end, check also if perhaps the variables aren’t changed somewhere else.
Yeah, it does look like the iteration variable is modified inside of the iteration, but the bigger problem is that the algorithm as coded is not mathematically correct. Not a lot of benefit in fixing an implementation that can’t work.
That mistake makes a huge difference. You aren’t really implementing this algorithm as described with your complex loop though.
Sieving with a mixed array (booleans and numbers) still is less efficient than only using a boolean array. Dynamically allocating that numbers array is still slow.
In any case, you will actually need all primes up to max for this algorithm to work.
You should not generate primes inside of this loop. That is a lot of repeated/wasted effort.
You should not modify n inside of this loop… In the best case, manual adjustment of the iteration variable is confusing. In the worst case, it is going to break your code.
I would actually step back and empty this function out and start with comments
function smallestCommons(arr) {
// 0 - Compute primes
// 1 - Prime factorization of each num in range
// 2 - Find maximum power of each prime
// 3 - Compute smallest common multiple
let scm;
// 4 - Return result
return scm;
}
I would then add some more comments about how to do each part before starting to add code.
Hello,
I took some holidays.
I resume the exercice this week and that works
function smallestCommons(arr) {
let max = Math.max(...arr);
let min = Math.min(...arr);
const dividedByIndex = [[0], [0]];
// 0 - I'm looking for the prime of n.(Compute primes)______________________________
let isPrime = Array(max + 1).fill(true);
// 0 and 1 are not prime
isPrime[0] = false;
isPrime[1] = false;
for (let i = 2; i <= Math.sqrt(max); i++) {
if (isPrime[i]) {
// if i has not been marked false -- it is a prime
for (let j = i * i; j <= max; j += i)
isPrime[j] = false;
}
}
console.log('the prime numbers less than n : ' + isPrime)
for (let n = min; n <= max; n++) {
//console.log('le chiffre n : ' + n);
let count = 0;
dividedByIndex.push([0,0]); // I added two zero in order to make match count with the index egal to prime[k]
// 1 - Prime factorization of each num in range._____________________________
for (let k = 2; k < isPrime.length; k++) {
//for each number n in the first for loop, I decompose over each prime number.
let n2 = n;
if (isPrime[k]) {
while (n2 % k == 0) {
n2 = n2 / k;
count++;
}
}
dividedByIndex[dividedByIndex.length - 1].push(count);
count = 0;
} // k loop
} // n loop
console.log('Primes factorization with count : ' + JSON.stringify(dividedByIndex));
// 2 - Find maximum power of each prime______________________________
let factorized = [];
for (let i = 0; i < dividedByIndex.length; i++) {
factorized.push([])
for (let j = 0; j < dividedByIndex[i].length; j++) {
if ( dividedByIndex[i][j] === 0 ) {
factorized[factorized.length-1].push(0) // because each number pow 0 egal 1
} else {
factorized[factorized.length-1].push(Math.pow(j, dividedByIndex[i][j]))
}
}
}
console.log(
'Product prime(index) by factorization(count) :' + JSON.stringify(factorized)
);
console.log(factorized[factorized.length - 1].length);
let factorizedByIndexGroup = [];
console.log(factorized[factorized.length - 1].length);
for (let i = 0; i < factorized[factorized.length - 1].length; i++) {
factorizedByIndexGroup.push([]);
for (let j = 0; j < factorized.length; j++) {
if (factorized[j][i] > 0) {
factorizedByIndexGroup[i].push(factorized[j][i]);
}
}
}
console.log('Power of each prime : ' + JSON.stringify(factorizedByIndexGroup));
// I delete the empty arrays:
let factorizedByIndexGroupfiltered = factorizedByIndexGroup.filter(
(x) => x.length > 0
);
console.log( factorizedByIndexGroupfiltered )
//factorizedByIndexGroupfiltered.reduce((a,b) => Math.max(...a) * Math.max(...b))
let maxPowerPrimes = factorizedByIndexGroupfiltered.map((x) => Math.max(...x));
console.log('maximum power of each primes : ' + maxPowerPrimes)
// 3 - Compute smallest common multiple (scm)__________________________
let scm = maxPowerPrimes.reduce((a,b) => a * b);
console.log(scm)
return scm
}
smallestCommons([2, 10]);
I really would be interrested to have your comments in order to improve it.
In part 2 I put this line as comment because it doesn’t work. Could you please say me if it’s possible or not ?
Good job getting it to work! It is a trick approach to take.
I think the biggest issue is that your code is very complex. You have a lot of pieces to keep track of that you can ultimately simplify
function smallestCommons(arr) {
const [min, max] = [...arr].sort((a, b) => a - b);
const range = Array(max - min + 1).fill(0).map((_, i) => i + min);
// Find all possible prime factors
const isPrime = Array(max + 1).fill(true);
isPrime[0] = false; isPrime[1] = false;
for (let i = 2; i < Math.sqrt(max); i++)
if (isPrime[i])
for (let j = i*i; j <= max; j+= i)
isPrime[j] = false;
// Compute and return SCM
return isPrime
// Find highest factor of each prime
.map(
(isPrime, i) => {
return !isPrime
? 1
: range
// Find highest power of prime for each num in range
.map((num) => {
let factor = 1;
while (num % i === 0) {
factor *= i; num /= i;
}
return factor;
})
// Find highest power of prime for all num in range
.reduce((a, b) => a > b ? a : b);
}
)
// Compute SCM
.reduce((product, num) => num * product)
}
console.log(smallestCommons([2, 10]));
I think it’s work trying to implement the GCD based algorithm. That is a particularly good approach.
Solving math focused problems like this one is a specialized skill that takes practice.
The bigger thing you should get from this challenge is breaking down a complicated problem and getting a solution that works. Once you get solutions that work, then you can practice refining them.
!!